題目鏈接：點擊查看

題目大意：給出 $A,B,C,D,E$，求 $sum$

題目分析：數位dp，開五維維護一下狀態即可，簡單說一下 $dp$ 的狀態：
$dp[pos][x>=A][x<=B][y>=C][y<=D][xor>E]$

如果是求方案數的話就非常簡單了，但本題需要求貢獻，實質上分成兩種情況來討論就可以做到不重不漏了：

$pos+1$ 位置之前異或和就大于 $e$

到 $pos+1$ 位置為止異或和還等于 $e$，$pos$ 為止開始異或和大于 $e$

累計貢獻是自上而下計算的，如果滿足上面的情況一，只需要維護本位的貢獻即可，如果滿足了上面的情況二，則需要將最高位到 $pos+1$ 的貢獻也累加上才行

代碼：

// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=110; const int mod=1e9+7; int A[70],B[70],C[70],D[70],E[70]; LL dp[70][2][2][2][2][2];//dp[pos][x>=A][x<=B][y>=C][y<=D][x xor y >E] LL a,b,c,d,e; LL dfs(int pos,int f1,int f2,int f3,int f4,int f5,LL now) {if(pos==-1) {return 0;}if(dp[pos][f1][f2][f3][f4][f5]!=-1) {return dp[pos][f1][f2][f3][f4][f5];}int downx=f1?A[pos]:0;int upx=f2?B[pos]:1;int downy=f3?C[pos]:0;int upy=f4?D[pos]:1;int downe=E[pos];LL ans=0;for(int i=downx;i<=upx;i++) {for(int j=downy;j<=upy;j++) {//前面卡住了xor，當前位小于e，不合法 if(!f5&&(i^j)<downe) {continue;}//前面卡住了xor，下面可能合法，繼續遞歸 ans=(ans+dfs(pos-1,f1&&i==downx,f2&&i==upx,f3&&j==downy,f4&&j==upy,f5||(i^j)>downe,now|((i^j)*(1LL<<pos))))%mod;//統計貢獻 LL dx=f1&&i==downx?((a&((1LL<<pos)-1)))%mod:0;LL ux=f2&&i==upx?((b&((1LL<<pos)-1)))%mod:((1LL<<pos)-1)%mod;LL dy=f3&&j==downy?((c&((1LL<<pos)-1)))%mod:0;LL uy=f4&&j==upy?((d&((1LL<<pos)-1)))%mod:((1LL<<pos)-1)%mod;LL x=(ux-dx+mod+1)%mod;LL y=(uy-dy+mod+1)%mod;if(f5) {//pos+1之前就大于了e LL val=((i^j)*(1LL<<pos))%mod;ans=(ans+val*x%mod*y%mod)%mod;} else if(!f5&&(i^j)>downe) {//pos+1卡住了e，pos大于了e LL val=((i^j)*(1LL<<pos)+now)%mod;ans=(ans+val*x%mod*y%mod)%mod;}}}return dp[pos][f1][f2][f3][f4][f5]=ans; } LL solve(LL a,LL b,LL c,LL d,LL e) {memset(dp,-1,sizeof(dp));for(int i=0;i<=62;i++) {A[i]=a&1;a>>=1;B[i]=b&1;b>>=1;C[i]=c&1;c>>=1;D[i]=d&1;d>>=1;E[i]=e&1;e>>=1;}return dfs(62,1,1,1,1,0,0); } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;int kase=0;while(w--) {read(a),read(b),read(c),read(d),read(e);printf("Case %d: %lld\n",++kase,solve(a,b,c,d,e));}return 0; }

總結

以上是生活随笔為你收集整理的FZU - 2042 The Mad Mathematician(数位dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。