题解 P4067 【[SDOI2016]储能表】
Fizzmy
·
·
题解
Solution：
看到两个求和符号下意识想到莫反...
等等 为什么莫反会有异或操作？？？
...
最终发现是一道二进制下的数位dp：
对于每个状态记录合法方案数和所有合法i,j的异或和，最后把k的那些减去即可
代码依旧套路，记忆化搜索即可
代码：
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#define pii pair<int,int>
using namespace std;
long long n,m,nn,mm,k,kk;
int T,mod,maxlen;
pii f[70][2][2][2];
bool vis[70][2][2][2];
void add(int &x,int y)
{
x+=y;
if (x>=mod) x-=mod;
}
pii dp(int len,bool n1,bool m1,bool k1)
{
if (len>maxlen) return make_pair(1,0);
if (vis[len][n1][m1][k1]) return f[len][n1][m1][k1];
vis[len][n1][m1][k1]=1;
int np=(n>>maxlen-len)&1,mp=(m>>maxlen-len)&1,kp=(k>>maxlen-len)&1;
for (int i=0;i<=(n1?np:1);i++)
for (int j=0;j<=(m1?mp:1);j++)
{
if (k1&&(i^j)<kp) continue;
pii nw=dp(len+1,n1&&(i==np),m1&&(j==mp),k1&&((i^j)==kp));
add(f[len][n1][m1][k1].first,nw.first);
add(f[len][n1][m1][k1].second,((1ll<<maxlen-len)*(i^j)%mod*nw.first+nw.second)%mod);
}
return f[len][n1][m1][k1];
}
int main()
{
scanf("%d",&T);
while (T--)
{
memset(vis,0,sizeof(vis));memset(f,0,sizeof(f));
scanf("%lld%lld%lld%d",&n,&m,&k,&mod);
n--,m--;
int nw=0;
nn=n,mm=m,kk=k;
while (nn) nw++,nn/=2;maxlen=max(nw,maxlen);nw=0;
while (mm) nw++,mm/=2;maxlen=max(nw,maxlen);nw=0;
while (kk) nw++,kk/=2;maxlen=max(nw,maxlen);
pii ans=dp(1,1,1,1);
printf("%d\n",(1ll*ans.second-1ll*k%mod*ans.first%mod+mod)%mod);
}
}
```