提出 #7063785

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
using namespace std;

template <int32_t MOD>
struct mint {
    int32_t value;
    mint() : value() {}
    mint(int64_t value_) : value(value_ < 0 ? value_ % MOD + MOD : value_ >= MOD ? value_ % MOD : value_) {}
    inline mint<MOD> operator + (mint<MOD> other) const { int32_t c = this->value + other.value; return mint<MOD>(c >= MOD ? c - MOD : c); }
    inline mint<MOD> & operator += (mint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; }
};

int64_t msb(int64_t n) {
    if (not n) return 0;
    return 1ull << (63 - __builtin_clzll(n));
}

constexpr int MOD = 1e9 + 7;
mint<MOD> solve(int64_t l, int64_t r) {
    array<array<mint<MOD>, 2>, 2> cur = {};
    for (int64_t i = 1ull << 62; i; i >>= 1) {
        array<array<mint<MOD>, 2>, 2> prv = cur;
        cur = {};
        if (msb(l) <= i and i <= msb(r)) {
            cur[i == msb(l)][i == msb(r)] += 1;
        }
        REP (p, 2) REP (q, 2) REP (xy, 3) {
            bool x = (xy >= 2);
            bool y = (xy >= 1);
            if (p and (l & i) and not x) continue;
            if (q and not (r & i) and y) continue;
            bool np = p and ((bool)(l & i) == x);
            bool nq = q and ((bool)(r & i) == y);
            cur[np][nq] += prv[p][q];
        }
    }
    mint<MOD> cnt = 0;
    REP (p, 2) REP (q, 2) {
        cnt += cur[p][q];
    }
    return cnt;
}

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

提出情報

ジャッジ結果