問題概要

$L$ と $R$ が与えられる。このとき $L \leq x \leq y \leq R$ かつ $( y \bmod x ) = ( y \oplus x )$ を満たす整数の組 $(x, y)$ の個数を求めよ。

(問題文は https://atcoder.jp/contests/abc138/tasks/abc138_f に記載されている。)

制約

$1 \leq L \leq R \leq 10^{18}$

アイディア

$1 \leq x \leq y$ の条件下で $(y \bmod x ) \leq (y - x ) \leq ( y \oplus x )$ が成り立つことが証明できる。よって， $( y \bmod x ) = ( y \oplus x )$ が成り立つときには必ず $( y - x ) = ( y \oplus x )$ が成り立つ。また，このとき $y$ を $x$ を割ったときの商は $1$ となる。逆に， $y$ を $x$ を割ったときの商は $1$ であるとき $(y \bmod x ) = ( y - x )$ が成り立つため，条件「 $( y \bmod x ) = ( y \oplus x )$ 」は条件「 $( y - x ) = ( y \oplus x )$ かつ $y$ を $x$ を割ったときの商が $1$ 」と言い換えられ，さらに $1 \leq x \leq y$ であるため条件「 $y$ を $x$ を割ったときの商が $1$ 」は $x \leq y \lt 2x$ と言い換えられ，最終的に「 $x \leq y$ かつ $\frac{y}{2} \lt x$ 」となる。よって，条件をまとめると以下の5つである。

$x \leq y$
$L \leq x$
$y \leq R$
$\dfrac{y}{2} \lt x$
$( y - x ) = ( y \oplus x )$

そして，実は $( y - x ) = ( y \oplus x )$ をあとは，上4つに関するフラグを持ちながら $( y - x ) = ( y \oplus x )$ を保つように遷移を行いつつ地道にDPを行えばよい。

2019/08/19追記: $( y - x ) = ( y \oplus x )$ が成り立つとき $x \leq y$ も成り立つため， $x \leq y$ に関するフラグは不必要です。コード例では $x \leq y$ に関するフラグを持たずに実装しています。

実装

$dp(i,a,b,c,d,p)$ を上から $i$ 桁目まで見てかつyの最後の桁が $p$ であるときの組み合わせの個数とする。ただし， $a,b,c,d$ はそれぞれ

$a$ : $x \leq y$ が確定しているかどうか
$b$ : $L \leq x$ が確定しているかどうか
$c$ : $y \leq R$ が確定しているかどうか
$d$ : $\dfrac{y}{2} \lt x$ が確定しているかどうか

を示すフラグである。

今見ている桁が上から $i$ 桁目であるとし， $L,R$ の上から $i$ 桁目をそれぞれ $l,r$ とし， $x, y$ に付け加える桁を $s, t$ とすると，

$a$ が false でかつ $s \gt t$ のとき $x \leq y$ ではないことが確定するので NG
$b$ が false でかつ $l \gt s$ のとき $L \leq x$ ではないことが確定するので NG
$c$ が false でかつ $t \gt r$ のとき $y \leq R$ ではないことが確定するので NG
$d$ が false でかつ $p \gt s$ のとき $\dfrac{y}{2} \lt x$ ではないことが確定するので NG
$x = 1$ かつ $y = 0$ のとき $( y - x ) = ( y \oplus x )$ ではないことが確定するので NG

これらのケースを除外したあとで

$e$ : $a$ が true または $s \lt t$ ならば true
$f$ : $b$ が true または $l \lt s$ ならば true
$g$ : $c$ が true または $t \lt r$ ならば true
$h$ : $d$ が true または $p \lt s$ ならば true

として， $dp(i+1,e,f,g,h,t)$ に $dp(i,a,b,c,d,p)$ を足せばよい。

計算量は $O(\log(R))$ であるが，定数が比較的重い。

2019/08/19追記: 先程のアイディアで追記したとおり，フラグ $a$ は不必要であるため下の実装例では持っていない。また，下の実装例ではフラグ $b, c, d$ をbitによって管理している。

コード

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
const ll MOD = (ll)(1e9+7);

ll dp[63][8][2];

int main(void){
    int i,j,k,l,r,p,s,t;
    ll L,R,ans=0ll;
    dp[0][0][0] = 1ll;
    cin >> L >> R;
    for(i=0; i<60; ++i){
        l = (!!(L&(1ll<<(59-i)))); r = (!!(R&(1ll<<(59-i))));
        for(s=0; s<2; ++s){
            for(t=0; t<2; ++t){
                    if(s==1 && t==0){
                        continue;
                    }
                for(j=0; j<8; ++j){
                    for(p=0; p<2; ++p){
                        if((!(j&1)) && (l > s)){
                            continue;
                        }
                        if((!(j&2)) && (t > r)){
                            continue;
                        }
                        if((!(j&4)) && (p > s)){
                            continue;
                        }
                        k = 0;
                        if((j&1) || (l < s)){
                            k += 1;
                        }
                        if((j&2) || (t < r)){
                            k += 2;
                        }
                        if((j&4) || (p < s)){
                            k += 4;
                        }
                        dp[i+1][k][t] += dp[i][j][p];
                        dp[i+1][k][t] %= MOD;
                    }
                }
            }
        }
    }
    for(j=0; j<8; ++j){
        for(p=0; p<2; ++p){
            if(!(j&4)){
                continue;
            }
            ans += dp[60][j][p];
            ans %= MOD;
        }
    }
    cout << ans << endl;
    return 0;
}

(提出したものはこちら)