CF809C（找规律+数位DP）

老年选手需要多写一些思维题qwq。

通过打表很容易发现对于(i,j)，值为(i-1)^(j-1)+1，然后本题就没了qwq。

矩阵差分还是很容易想到的，容斥成四个矩阵。

然后看到异或很容易想到三件事：数位DP、字典树、线性基。很容易发现后两种与本题不符，就是数位DP了，从高位到低位DP，f[i][0/1][0/1][0/1]表示到第i位，当前的x、y、x^y是否达到上界，然后直接暴力枚举当前位即可。因为q<=1e4怕memset多了出事，我用了滚动数组qwq。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=3e5+,mod=1e9+;

int f[][][][],g[][][][];

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<||m<)return ;

    memset(f,,sizeof f),memset(g,,sizeof g);

    int p=;

    g[][][][]=;

    for(int i=;~i;i--)

    {

        int x=n>>i&,y=m>>i&,z=k>>i&;

        for(int j=;j<=;j++)

        for(int k=;k<=;k++)

        for(int l=;l<=;l++)

        if(g[p^][j][k][l])

        {

            for(int X=;X<=(x|(!j));X++)

            for(int Y=;Y<=(y|(!k));Y++)

            if((X^Y)<=z||!l)

            {

                add(f[p][j&(X==x)][k&(Y==y)][l&((X^Y)==z)],(f[p^][j][k][l]+1ll*g[p^][j][k][l]*((X^Y)<<i)%mod)%mod);

                add(g[p][j&(X==x)][k&(Y==y)][l&((X^Y)==z)],g[p^][j][k][l]);

            }

            f[p^][j][k][l]=g[p^][j][k][l]=;

        }

        p^=;

    }

    int ans=;

    for(int j=;j<=;j++)

    for(int k=;k<=;k++)

    for(int l=;l<=;l++)

    add(ans,(f[p^][j][k][l]+g[p^][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-,by,k)-work(bx,ay-,k)+work(ax-,ay-,k))%mod+mod)%mod);

    }

}

巴特西

CF809C（找规律+数位DP）

最新文章

热门文章