对网站建设和维护好学吗,做海报创客贴同类网站,桂林网站建设桂林,网站专题页面案例传送门 数位dp卡常题。 写了一发dfs版本的发现过不了233。 于是赶紧转循环版本。 预处理出f数组。f[i][j]f[i][j]f[i][j]表示前i位数异或和为j的方案数。 然后每次直接数位dp就行了。 代码#xff1a; #includebits/stdc.h
#define mod 1000000007
#define N 100005
#… 传送门 数位dp卡常题。 写了一发dfs版本的发现过不了233。 于是赶紧转循环版本。 预处理出f数组。f[i][j]f[i][j]f[i][j]表示前i位数异或和为j的方案数。 然后每次直接数位dp就行了。 代码 #includebits/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 i0;i10;i)f[1][i]1;for(int i2;i100001;i)for(int k0;k10;k)for(int j0;j16;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 lenstrlen(s),sum0;ll ret0;for(int i1;ilen;i)num[i]s[i-1]-0;for(int i1;ilen;i){for(int j0;jnum[i];j)for(int k0;k16;k)(ans[k]f[len-i][sum^j^k]);sum^num[i];}for(int i0;i16;i)(ret1ll*i*ans[i])%mod;return ret;
}
char s[N],t[N];
int main(){scanf(%d,T),init();for(int i1;iT;i){scanf(%s%s,s,t);int tmp0,lenstrlen(t);for(int j0;jlen;j)tmp^t[j]-0;printf(Case #%d: %lld\n,i,((solve(t)-solve(s)tmp)%modmod)%mod);}return 0;
}转载于:https://www.cnblogs.com/ldxcaicai/p/9738184.html
