[数位DP][模板][二进制性质] SDOI2016 储能表

题目链接

题意：给定n, m, k, p, 求出
\[
\sum_{i=0}^{n-1}\sum_{j=0}^{m-1} max(i\oplus j-k)\\
最大数据范围
T = 5000， n \leq 10 ^ {18} ， m \leq 10 ^ {18} ， k \leq 10 ^ {18} ， p \leq 10 ^ 9
\]

题解：转化成求\[\sum_{i=0}^{n-1}\sum_{j=0}^{m-1} i\oplus j*\epsilon(i\oplus j-k) – k*\sum_{i=0}^{n-1}\sum_{j=0}^{m-1} 1*\epsilon(i\oplus j-k)\]，其中\[\epsilon(x)当x> 0时为1，否则为0\]. 这样的话可以直接数位dp计算了，有两个范围和一个约束，要计算的量也有两个，刚学到的kuangbin的板子十分的好用！！！这个甩锅给-1位的写法真的太简洁了。

error：第一个是搞错了当前位的贡献，只乘上了二进制位的权值，没有乘后面的种类数。第二个是爆int，日常long long错误

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

ll n,m,k,p;
ll dp1[70][2][2][2],dp2[70][2][2][2];
int nb[70],mb[70],kb[70];
ll pre[70];

void add(ll& a,ll b){
    a=(a+b>=p?a+b-p:a+b);
}

ll dfs1(int pos,int n1,int m1,int k1,ll& w){
    if(pos==-1){
        if(k1==0&&n1==0&&m1==0) return 1;
        else return 0;
    }
    if(dp1[pos][n1][m1][k1]!=-1){
        w=dp2[pos][n1][m1][k1];
        return dp1[pos][n1][m1][k1];
    } 
    int endn=(n1?nb[pos]:1);
    int endm=(m1?mb[pos]:1);
    ll ans=0,tmp=0,pw=0;
    for(int i=0;i<=endn;i++)
        for(int j=0;j<=endm;j++){
            pw=0;
            if(k1&&(i^j)<kb[pos]) continue;
            tmp=dfs1(pos-1,n1&&i==endn,m1&&j==endm,k1&&(i^j)==kb[pos],pw);
            if(tmp>=p) tmp%=p;
            if(tmp){
                add(ans,tmp);
                add(w,(pw+(i^j)*pre[pos]*tmp)%p);
            }
        }
    dp2[pos][n1][m1][k1]=w;
    return dp1[pos][n1][m1][k1]=ans;
}

void work(){
    for(int i=0;i<=62;i++){
        pre[i]=(int)((1LL<<i)%p);
    }
    memset(dp1,-1,sizeof(dp1));
    memset(dp2,-1,sizeof(dp2));
    int pos=0;ll tk=k;//error2
    while(n||m||k){
        nb[pos]=(n&1),mb[pos]=(m&1),kb[pos]=(k&1);
        n>>=1,m>>=1,k>>=1;
        pos++;
    }
    ll ans1=0,ans2=0;
    ans1=dfs1(pos-1,1,1,1,ans2);
    tk%=p;
    ans1%=p;
    printf("%lld\n",((ans2-tk*ans1%p)%p+p)%p);//error1
}

void bruteforce(){
    ll p1=0,p2=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if((i^j)>k){
                p1++;
                p2+=(i^j);
            }
        }
    }
    // cout<<p1%p<<" "<<p2%p<<endl;
}

int main()
{
    // freopen("1.txt","r",stdin);
    // freopen("2.txt","w",stdout);
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%lld%lld%lld%lld",&n,&m,&k,&p);
        //bruteforce();
        work();
    }
    return 0;
}
/*
1
504363800392059286 554192717354508770 21453916680846604 401134357
*/