数位DP+剪枝，本题卡$10^3的数位DP。理解还是不够深刻。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=33;
const int mod=1e9+7;
//定义f(i,j,k)
//到第i位位置，x是否卡死，y是否卡死，前面是否全是0的贡献。
ll f[maxn][2][2][2];
int a[100],b[maxn],len1,len2;
ll L,R;
ll dfs (int pos,int limit1,int limit2,int st) {
//printf("%d %d
",j,k);
if (pos<=0) {
return 1;
}
if (f[pos][limit1][limit2][st]!=-1) return f[pos][limit1][limit2][st]%mod;
ll ans=0;
ll k1=limit1?a[pos]:1;
ll k2=limit2?b[pos]:1;
for (int x=0;x<=k1;x++) {
for (int y=0;y<=k2;y++) {
if (x&&y) continue;
int tt;
if (st&&(x||y)) tt=pos;
else tt=1;
ans+=1ll*tt*dfs(pos-1,limit1&&x==k1,limit2&&y==k2,st&&!x&&!y)%mod;
ans%=mod;
}
}
f[pos][limit1][limit2][st]=ans;
return ans;
}
ll solve (ll L,ll R) {
len1=0,len2=0;
while (L) {
a[++len1]=L%2;
L/=2;
}
while (R) {
b[++len2]=R%2;
R/=2;
}
while (len1<len2) a[++len1]=0;
while (len2<len1) b[++len2]=0;
memset(f,-1,sizeof(f));
return dfs(len1,1,1,1);
}
int main () {
int _;
cin>>_;
while (_--) {
ll L,R;
scanf("%lld%lld",&L,&R);
cout<<solve(L,R)-1<<'
';
}
}