传送门
数位dp卡常题。
写了一发dfs版本的发现过不了233。
于是赶紧转循环版本。
预处理出f数组。
f[i][j]f[i][j]f[i][j]表示前i位数异或和为j的方案数。
然后每次直接数位dp就行了。
代码：
#include<bits/stdc++.h>
#define mod 1000000007
#define N 100005
#define ll long long
using namespace std;
ll f[N][16],ans[16];
inline void init(){
f[0][0]=1;
for(int i=0;i<10;++i)f[1][i]=1;
for(int i=2;i<=100001;++i)for(int k=0;k<10;++k)for(int j=0;j<16;++j)(f[i][j^k]+=f[i-1][j])%=mod;
}
int T,num[N];
inline ll solve(char s[]){
memset(ans,0,sizeof(ans));
int len=strlen(s),sum=0;
ll ret=0;
for(int i=1;i<=len;++i)num[i]=s[i-1]-'0';
for(int i=1;i<=len;++i){
for(int j=0;j<num[i];++j)for(int k=0;k<16;++k)(ans[k]+=f[len-i][sum^j^k]);
sum^=num[i];
}
for(int i=0;i<16;++i)(ret+=1ll*i*ans[i])%=mod;
return ret;
}
char s[N],t[N];
int main(){
scanf("%d",&T),init();
for(int i=1;i<=T;++i){
scanf("%s%s",s,t);
int tmp=0,len=strlen(t);
for(int j=0;j<len;++j)tmp^=t[j]-'0';
printf("Case #%d: %lld\n",i,((solve(t)-solve(s)+tmp)%mod+mod)%mod);
}
return 0;
}