老年選手需要多寫一些思維題qwq。

通過打表很容易發(fā)現(xiàn)對于(i,j)，值為(i-1)^(j-1)+1，然后本題就沒了qwq。

矩陣差分還是很容易想到的，容斥成四個矩陣。

然后看到異或很容易想到三件事：數(shù)位DP、字典樹、線性基。很容易發(fā)現(xiàn)后兩種與本題不符，就是數(shù)位DP了，從高位到低位DP，f[i][0/1][0/1][0/1]表示到第i位，當(dāng)前的x、y、x^y是否達(dá)到上界，然后直接暴力枚舉當(dāng)前位即可。因?yàn)閝<=1e4怕memset多了出事，我用了滾動數(shù)組qwq。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=3e5+10,mod=1e9+7; int f[2][2][2][2],g[2][2][2][2]; void add(int&x,int y){x=x+y>=mod?x+y-mod:x+y;} ll work(int n,int m,int k) {if(n<0||m<0)return 0;memset(f,0,sizeof f),memset(g,0,sizeof g);int p=1;g[0][1][1][1]=1;for(int i=30;~i;i--){int x=n>>i&1,y=m>>i&1,z=k>>i&1;for(int j=0;j<=1;j++)for(int k=0;k<=1;k++)for(int l=0;l<=1;l++)if(g[p^1][j][k][l]){for(int X=0;X<=(x|(!j));X++)for(int Y=0;Y<=(y|(!k));Y++)if((X^Y)<=z||!l){add(f[p][j&(X==x)][k&(Y==y)][l&((X^Y)==z)],(f[p^1][j][k][l]+1ll*g[p^1][j][k][l]*((X^Y)<<i)%mod)%mod);add(g[p][j&(X==x)][k&(Y==y)][l&((X^Y)==z)],g[p^1][j][k][l]);}f[p^1][j][k][l]=g[p^1][j][k][l]=0;}p^=1;}int ans=0;for(int j=0;j<=1;j++)for(int k=0;k<=1;k++)for(int l=0;l<=1;l++)add(ans,(f[p^1][j][k][l]+g[p^1][j][k][l])%mod);return ans; } int main() {int T;scanf("%d",&T);while(T--){int ax,ay,bx,by,k;scanf("%d%d%d%d%d",&ax,&ay,&bx,&by,&k);ax--,ay--,bx--,by--,k--;printf("%lld\n",((work(bx,by,k)-work(ax-1,by,k)-work(bx,ay-1,k)+work(ax-1,ay-1,k))%mod+mod)%mod);} } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/hfctf0210/p/10975780.html

總結(jié)

以上是生活随笔為你收集整理的CF809C（找规律+数位DP）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。