题目背景
NOIP2018初赛结束了，但H还是要上学的啊啊。。上学肯定要完成老师布置的作业，H十分头疼。在如山的作业中，Mr.G布置的数学作业最烦人，H总是完不成~~
题目描述
Mr.G最近在看一些关于数字题的书，他每天愁同学们太聪明了，所有的作业同学们都能做到全对（拿到答案）。Mr.G蒙在鼓里（心知肚明）。为了使同学们进步，Mr.G总是创造一些简单（毒瘤）题来作为作业。以下是数学作业的最后一题题干——
给出一个区间LL~RR，求LL到RR区间内每个数的数字和，如123这个数的数字和为1+2+3=6。
（1 leq L leq R leq 10^21≤L≤R≤102）
同学们纷纷做出来了，Mr.G一看这最后一题跟摆设没区别了呀，于是他迅速修改了题目，把范围定得非常非常大，且有TT组数据，将最终的答案mod 10^9+7109+7。
（1 leq L leq R leq 10^{18}1≤L≤R≤1018） （1 leq T leq 201≤T≤20）
同学们纷纷被难住了。但H为了备战NOIP2018，没有时间完成Mr.G的数学作业（其实是不想做QwQ），所以Ta找到了你，希望你帮助Ta和同学完成这烦人的数学作业！
#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<<'
';
}
}