Language: C++

// 解説後
#include <array>
#include <iostream>

// xのMSBをn、yのMSBをmとする。
// n>mとすると、x>yとなり条件（x<=y）と矛盾するので、無視して良い。
// n<mとすると、y^x>x>(y mod x)となるので、数えなくて良い。
// => n=mのときだけを考えれば良い。

// このとき、y/xの商は1なので、(y mod x) = y-xとなり、考慮すべき条件はy-x=y^xとなる。
// => すべての桁において繰り下がりが起こらない組を数えれば良い。
// => i∈[0,m)において、i桁目のビット(x_i, y_i)が(1, 0)でない組を数えれば良い。
//
// 計算の効率性を高めるため、個数を累積的に数えたい。
// => 各条件が真かどうかで個数を分割して記録することを考える。
//    その条件は「x>=L」、「y<=R」、「MSBが一致する」の3つ。
//
// iビット目までを見たとき、(i+1)ビット目に値を加えるとする。
// (i+1)ビットまでを見たときの個数を加えた値によって変化した条件とともに記録する。
// => 最終的に、63ビット目までを見たときに条件がすべて真となる組の個数を計算できる。

// 条件を満たすかどうかのフラグ
constexpr uint32_t COND_L_BIT = 0b100;     // xがL以上かどうか
constexpr uint32_t COND_R_BIT = 0b010;     // yがR以下かどうか
constexpr uint32_t COND_MSB_BIT = 0b001;   // MSBが一致するか
constexpr uint32_t COND_ALL_BITS = 0b111;  // すべてを満たすか

template <typename T, size_t ROWS, size_t COLUMNS>
using Array2D = std::array<std::array<T, COLUMNS>, ROWS>;

int solve_F() {
  uint64_t L;  // 下限
  uint64_t R;  // 上限
  std::cin >> L >> R;

  // 0ビット目に値を加えたときの個数を記録する
  Array2D<uint64_t, 64, 8> counts{};  // [見た最大ビット][条件フラグのビットセット]
  auto f0 = [&](auto y, auto x) {
    size_t cond = 0;
    if (x >= (L & 1)) cond |= COND_L_BIT;
    if (y <= (R & 1)) cond |= COND_R_BIT;
    if (x == y) cond |= COND_MSB_BIT;

    counts[0][cond] += 1;
  };
  f0(0, 0);
  f0(1, 0);
  f0(1, 1);

  // 各条件に沿った組の個数を累積的に計算する
  for (size_t i = 0; i < counts.size() - 1; ++i) {
    const auto l = (L >> (i + 1)) & 1;  // Lの(i+1)ビット目の値
    const auto r = (R >> (i + 1)) & 1;  // Rの(i+1)ビット目の値

    for (uint32_t cond = 0; cond < 8; ++cond) {
      // condの状態の組の(i+1)ビット目に(x, y)を付け加えたときの個数を累積的に記録する
      auto f = [&](auto y, auto x) {
        size_t new_cond = 0;
        if (x == l) {
          new_cond |= cond & COND_L_BIT;
        } else if (x >= l) {
          new_cond |= COND_L_BIT;
        }

        if (y == r) {
          new_cond |= cond & COND_R_BIT;
        } else if (y <= r) {
          new_cond |= COND_R_BIT;
        }

        if (x == 0 && y == 0) {
          new_cond |= cond & COND_MSB_BIT;
        } else if (x == 1 && y == 1) {
          new_cond |= COND_MSB_BIT;
        }

          counts[i + 1][new_cond] += counts[i][cond] % 1'000'000'007;
        };
        f(0, 0);
        f(1, 0);
        f(1, 1);
      }
    }

    // 結果発表
    std::cout << counts[63][COND_ALL_BITS];

    return 0;
  }

  int main() { return solve_F(); }


Compiler output:
a.cc:23:11: error: 'uint32_t' does not name a type
   23 | constexpr uint32_t COND_L_BIT = 0b100;     // xがL以上かどうか
      |           ^~~~~~~~
a.cc:4:1: note: 'uint32_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
    3 | #include <iostream>
  +++ |+#include <cstdint>
    4 | 
a.cc:24:11: error: 'uint32_t' does not name a type
   24 | constexpr uint32_t COND_R_BIT = 0b010;     // yがR以下かどうか
      |           ^~~~~~~~
a.cc:24:11: note: 'uint32_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
a.cc:25:11: error: 'uint32_t' does not name a type
   25 | constexpr uint32_t COND_MSB_BIT = 0b001;   // MSBが一致するか
      |           ^~~~~~~~
a.cc:25:11: note: 'uint32_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
a.cc:26:11: error: 'uint32_t' does not name a type
   26 | constexpr uint32_t COND_ALL_BITS = 0b111;  // すべてを満たすか
      |           ^~~~~~~~
a.cc:26:11: note: 'uint32_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
a.cc: In function 'int solve_F()':
a.cc:32:3: error: 'uint64_t' was not declared in this scope
   32 |   uint64_t L;  // 下限
      |   ^~~~~~~~
a.cc:32:3: note: 'uint64_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
a.cc:33:11: error: expected ';' before 'R'
   33 |   uint64_t R;  // 上限
      |           ^~
      |           ;
a.cc:34:15: error: 'L' was not declared in this scope
   34 |   std::cin >> L >> R;
      |               ^
a.cc:34:20: error: 'R' was not declared in this scope
   34 |   std::cin >> L >> R;
      |                    ^
a.cc: In lambda function:
a.cc:40:31: error: 'COND_L_BIT' was not declared in this scope
   40 |     if (x >= (L & 1)) cond |= COND_L_BIT;
      |                               ^~~~~~~~~~
a.cc:41:31: error: 'COND_R_BIT' was not declared in this scope
   41 |     if (y <= (R & 1)) cond |= COND_R_BIT;
      |                               ^~~~~~~~~~
a.cc:42:25: error: 'COND_MSB_BIT' was not declared in this scope
   42 |     if (x == y) cond |= COND_MSB_BIT;
      |                         ^~~~~~~~~~~~
a.cc:44:11: error: invalid types 'int[int]' for array subscript
   44 |     counts[0][cond] += 1;
      |           ^
a.cc: In function 'int solve_F()':
a.cc:51:33: error: request for member 'size' in 'counts', which is of non-class type 'int'
   51 |   for (size_t i = 0; i < counts.size() - 1; ++i) {
      |                                 ^~~~
a.cc:55:10: error: 'uint32_t' was not declared in this scope
   55 |     for (uint32_t cond = 0; cond < 8; ++cond) {
      |          ^~~~~~~~
a.cc:55:10: note: 'uint32_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
a.cc:55:29: error: 'cond' was not declared in this scope
   55 |     for (uint32_t cond = 0; cond < 8; ++cond) {
      |                             ^~~~
a.cc: In lambda function:
a.cc:60:30: error: 'COND_L_BIT' was not declared in this scope
   60 |           new_cond |= cond & COND_L_BIT;
      |                              ^~~~~~~~~~
a.cc:62:23: error: 'COND_L_BIT' was not declared in this scope
   62 |           new_cond |= COND_L_BIT;
      |                       ^~~~~~~~~~
a.cc:66:30: error: 'COND_R_BIT' was not declared in this scope
   66 |           new_cond |= cond & COND_R_BIT;
      |                              ^~~~~~~~~~
a.cc:68:23: error: 'COND_R_BIT' was not declared in this scope
   68 |           new_cond |= COND_R_BIT;
      |                       ^~~~~~~~~~
a.cc:72:30: error: 'COND_MSB_BIT' was not declared in this scope
   72 |           new_cond |= cond & COND_MSB_BIT;
      |                              ^~~~~~~~~~~~
a.cc:74:23: error: 'COND_MSB_BIT' was not declared in this scope
   74 |           new_cond |= COND_MSB_BIT;
      |                       ^~~~~~~~~~~~
a.cc:77:17: error: invalid types 'int[size_t {aka long unsigned int}]' for array subscript
   77 |           counts[i + 1][new_cond] += counts[i][cond] % 1'000'000'007;
      |                 ^
a.cc:77:44: error: invalid types 'int[size_t {aka long unsigned int}]' for array subscript
   77 |           counts[i + 1][new_cond] += counts[i][cond] % 1'000'000'007;
      |                                            ^
a.cc: In function 'int solve_F()':
a.cc:86:24: error: invalid types 'int[int]' for array subscript
   86 |     std::cout << counts[63][COND_ALL_BITS];
      |                        ^
a.cc:86:29: error: 'COND_ALL_BITS' was not declared in this scope
   86 |     std::cout << counts[63][COND_ALL_BITS];
      |                             ^~~~~~~~~~~~~