BZOJ4513 SDOI2016储能表（数位dp）

　　如果n、m、k都是2的幂次方，答案非常好统计。于是容易想到数位dp，考虑每一位是否卡限制即可，即设f[i][0/1][0/1][0/1]为第i位是/否卡n、m、k的限制时，之前的位的总贡献；g[i][0/1][0/1][0/1]为第i位是/否卡n、m、k的限制时，之前的位的方案数。为了方便可以改为统计小于k的贡献再减去。

　　莫名其妙的搞错了很多地方，简直调一年，不知道在干啥。

　　人丑常数大，根本没办法。

　　（突然发现以前大部分数位dp都是直接按位计数就搞出来了……这个题应该也行。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 64

ll read()

{

    ll x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int T,p,f[N][][][],g[N][][][],a[N],b[N],c[N],q[N];

ll n,m,k;

void inc(int &x,int y,int p){x+=y;if (x>=p) x-=p;}

void calc(ll n,ll m,ll k,int p)

{

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

    int t=-;ll x=max(max(n,m),k);

    while (x) t++,x>>=;

    for (int i=;i<=t;i++) a[i]=(n&(1ll<<i))>;

    for (int i=;i<=t;i++) b[i]=(m&(1ll<<i))>;

    for (int i=;i<=t;i++) c[i]=(k&(1ll<<i))>;

    g[t+][][][]=;

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

        for (register int x=;x<=;x++)

            for (register int y=;y<=;y++)

                for (register int z=;z<=;z++)

                    for (register int u=x;u<=;u++)

                        for (register int v=y;v<=;v++)

                            for (register int w=z;w<=;w++)

                            {

                                int t=(!w|c[i]&z)?(((!u|a[i]&x)&(!v|b[i]^y))+((!v|b[i]&y)&(!u|a[i]^x))):;

                                inc(f[i][x][y][z],1ll*q[i]*g[i+][u][v][w]%p*t%p,p);

                                if (!w|c[i]^z) t+=(((!u|a[i]&x)&(!v|b[i]&y))+((!u|a[i]^x)&(!v|b[i]^y)));

                                inc(f[i][x][y][z],1ll*f[i+][u][v][w]*t%p,p);

                                inc(g[i][x][y][z],1ll*g[i+][u][v][w]*t%p,p);

                            }

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj4513.in","r",stdin);

    freopen("bzoj4513.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    T=read();

    while (T--)

    {

        n=read()-,m=read()-,k=read(),p=read();

        q[]=;for (int i=;i<=;i++) q[i]=(q[i-]<<)%p;

        int ans=;

        calc(n,m,max(n,m)<<,p);

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

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

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

                inc(ans,f[][x][y][z],p),inc(ans,p-1ll*k%p*g[][x][y][z]%p,p);

        calc(n,m,k,p);

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

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

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

                inc(ans,p-f[][x][y][z],p),inc(ans,1ll*k%p*g[][x][y][z]%p,p);

        cout<<ans<<endl;

    }

    return ;

}