提出 #7039762

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define N (long long)(1e9 + 7)
#define fin 61
using namespace std;

long long l, r;
long long dp[70][2][2];

long long solve();
long long cnt(long long nowl, long long nowr,
              long long dig);
bool ch(long long x, long long d);

int main() {
  cin >> l >> r;
  cout << solve() << endl;
  return 0;
}

long long solve() {
  long long ans = 0;
  for(int i = 0; i < fin; ++i) {
    long long nbase = 1LL << i, nmax = (1LL << (i + 1)) - 1;
    if(nmax < l || nbase > r) continue;
    ans +=
        cnt(max(nbase, l) - nbase, min(r, nmax) - nbase, i);
    ans %= N;
  }
  return ans;
}

long long cnt(long long nowl, long long nowr,
              long long dig) {
  for(int i = 0; i <= dig; ++i)
    for(int j = 0; j < 2; ++j)
      for(int k = 0; k < 2; ++k) dp[i][j][k] = 0;
  long long ans = 0;
  // i l r
  dp[0][0][0] = 1;
  for(int i = 0; i < dig; ++i) {
    bool flagr = ch(nowr, dig - 1 - i),
         flagl = ch(nowl, dig - 1 - i);
    if(flagr && flagl) {
      // use 1 1
      for(int j = 0; j < 2; ++j)
        for(int k = 0; k < 2; ++k)
          dp[i + 1][j][k] = dp[i][j][k];
      // use 0 1
      for(int j = 0; j < 2; ++j) {
        dp[i + 1][1][j] += dp[i][1][j];
        dp[i + 1][1][j] %= N;
      }
      // use 0 0
      dp[i + 1][1][1] += (dp[i][1][0] + dp[i][1][1]) % N;
      dp[i + 1][1][1] %= N;
    }
    else if(flagr) {
      // use 1 1
      for(int j = 0; j < 2; ++j)
        dp[i + 1][1][j] = (dp[i][0][j] + dp[i][1][j]) % N;
      // use 0 1
      for(int j = 0; j < 2; ++j)
        for(int k = 0; k < 2; ++k) {
          dp[i + 1][j][k] += dp[i][j][k];
          dp[i + 1][j][k] %= N;
        }
      // use 0 0
      for(int j = 0; j < 2; ++j) {
        dp[i + 1][j][1] += (dp[i][j][1] + dp[i][j][0]) % N;
        dp[i + 1][j][1] %= N;
      }
    }
    else if(flagl) {
      // use 1 1
      for(int j = 0; j < 2; ++j)
        dp[i + 1][j][1] = dp[i][j][1];
      // use 0 1
      dp[i + 1][1][1] += dp[i][1][1];
      dp[i + 1][1][1] %= N;
      // use 0 0
      for(int j = 0; j < 2; ++j) {
        dp[i + 1][1][j] += dp[i][1][j];
        dp[i + 1][1][j] %= N;
      }
    }
    else {
      // use 1 1
      dp[i + 1][1][1] = (dp[i][1][1] + dp[i][0][1]) % N;
      // use 0 1
      for(int j = 0; j < 2; ++j) {
        dp[i + 1][j][1] += dp[i][j][1];
        dp[i + 1][j][1] %= N;
      }
      // use 0 0
      for(int j = 0; j < 2; ++j)
        for(int k = 0; k < 2; ++k) {
          dp[i + 1][j][k] += dp[i][j][k];
          dp[i + 1][j][k] %= N;
        }
    }
  }
  for(int i = 0; i < 2; ++i)
    for(int j = 0; j < 2; ++j) {
      ans += dp[dig][i][j];
      ans %= N;
    }
  return ans;
}

bool ch(long long x, long long d) { return (x >> d) & 1; }

提出情報

ジャッジ結果