Submission #7101990


Source Code Expand

Copy
#include <bits/stdc++.h>

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

template <std::int64_t M>
class modint {
 public:
  int64_t a;

  explicit constexpr modint(const int64_t x = 0) noexcept : a((x % M + M) % M) {}
  constexpr int64_t &value() noexcept { return a; }
  constexpr const int64_t &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= M) {
      a -= M;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += M;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % M;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    int64_t exp = M - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
};

// L<=X<=Y<=R と Y%X = Y^X が条件
// まず場合分けをする
// 1) X = Y の場合、Y%X = Y^X == 0 なのでOK
// 2) X < Y の場合
//  2A) 2進数でXとYの桁数が同じ
//    Y^X = Y+X-2(Y&X)
//    Y%X = Y-X なぜならX<Y<2XよりY/X=1なので
//    つまり、X = X ^ Y
//    ある桁においてX=1でY=0はNG(そのほかの3つの場合でOK)
//  2B) 2進数でXとYの桁数が同じ
//    NG Y%Xは1から始まり、MODは0から始まるため

// dp[i][j][k][s]: 上からi桁番目まで見た時の個数。 
// jはX>=Lが確定しているかどうか
// kはY<=Rが確定しているかどうか
// sは先頭ビットが既に現れたかどうか

using mint = modint<1000000007>;
mint dp[64][2][2][2];

signed main() {
  ll L, R;
  cin >> L >> R;

  dp[63][0][0][0] = mint(1);
  for (ll i = 63; i>=1; i--) rep(j,2) rep(k,2) rep(s,2) {
    mint cur = dp[i][j][k][s];

    rep(x,2) rep(y,2) {
      if (x == 1 && y == 0) continue;

      ll ni = i - 1, nj = j, nk = k, ns = s;
      ll lb = (L>>ni) & 1;
      ll rb = (R>>ni) & 1;

      // j: X>=Lの判定
      if (!nj && lb == 1 && x == 0) continue;
      if (lb == 0 && x == 1) nj = 1;

      // k: Y<=Rの判定
      if (!nk && rb == 0 && y == 1) continue;
      if (rb == 1 && y == 0) nk = 1;

      // s: 先頭ビットが既出か判定
      if (!ns && (x^y == 1)) continue;
      if (x == 1 && y == 1) ns = 1;

      dp[ni][nj][nk][ns] += cur;
    }
  }

  mint ans(0);
  rep(j,2) rep(k,2) rep(s,2) {
    ans += dp[0][j][k][s];
  }
  cout << ans.value() << endl;
  return 0;
}

Submission Info

Submission Time
Task F - Coincidence
User bobuhiro11
Language C++14 (GCC 5.4.1)
Score 600
Code Size 3180 Byte
Status
Exec Time 1 ms
Memory 256 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 a01, a02, a03
All 600 / 600 a01, a02, a03, b04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23
Case Name Status Exec Time Memory
a01 1 ms 256 KB
a02 1 ms 256 KB
a03 1 ms 256 KB
b04 1 ms 256 KB
b05 1 ms 256 KB
b06 1 ms 256 KB
b07 1 ms 256 KB
b08 1 ms 256 KB
b09 1 ms 256 KB
b10 1 ms 256 KB
b11 1 ms 256 KB
b12 1 ms 256 KB
b13 1 ms 256 KB
b14 1 ms 256 KB
b15 1 ms 256 KB
b16 1 ms 256 KB
b17 1 ms 256 KB
b18 1 ms 256 KB
b19 1 ms 256 KB
b20 1 ms 256 KB
b21 1 ms 256 KB
b22 1 ms 256 KB
b23 1 ms 256 KB