Submission #9921525

---

Source Code Expand

#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...)name
#define _rep(i,n)repi(i,0,n)
#define repi(i,a,b)for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x)x
#define rep(...)MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c)c.begin(),c.end()
#define write(x)cout<<(x)<<'\n'
using namespace std; typedef long long ll; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

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

    constexpr int N = 60;
    vector<bool> Lbit(N), Rbit(N);
    rep(i, N) Lbit[i] = L >> (N - 1 - i) & 1;
    rep(i, N) Rbit[i] = R >> (N - 1 - i) & 1;
    int LM = 0, RM = 0;
    rep(i, N) {
        if (L >> i & 1) LM = N - 1 - i;
        if (R >> i & 1) RM = N - 1 - i;
    }

    vv<ll> dp = vvec(N, 4, 0LL);
    ll ans = 0;
    rep(m, RM, LM + 1) {
        rep(i, N) rep(r, 4) dp[i][r] = 0;
        dp[m][(m == RM) + 2 * (m == LM)] = 1;
        rep(i, m + 1, N) {
            rep(y, 2) rep(x, 2) rep(a, 2) rep(b, 2) rep(c, 2) rep(d, 2) {
                if (y < x) continue;
                if (a < c) continue;
                if (a != c && y >= Rbit[i]) continue;
                if (a == 1 && c == 1 && y != Rbit[i]) continue;
                if (b < d) continue;
                if (b != d && x <= Lbit[i]) continue;
                if (b == 1 && d == 1 && x != Lbit[i]) continue;
                dp[i][c + 2 * d] += dp[i - 1][a + 2 * b];
                dp[i][c + 2 * d] %= MOD;
            }
        }
        rep(r, 4) ans = (ans + dp[N - 1][r]) % MOD;
    }
    write(ans);
}

Submission Info

Judge Result