【BZOJ4513】[SDOI2016] 储能表（数位DP）

点此看题面

大致题意： 给定\(n,m,k\)，求\(\sum_{i=0}^{n-1}\sum_{j=0}^{m-1}max((i\ xor\ j)-k,0)\)。

前言

早上来机房做数学作业，结果一个不等式证明暴拆了一百多项，而且算到一半感觉不太对劲，心态爆炸。

于是把数学扔一边，先开始做题，于是就找到了这道题。

然后发现是好水一道数位\(DP\)啊。。。（反正比我的数学作业简单多了）

本来应该可以一发\(A\)的，结果数组没清干净\(WA\)成了\(20\)分。

（水完这篇博客继续肝数学。。。）

数位\(DP\)

首先，把\(n,m,k\)转化为二进制。

然后，我们设\(f_{x,0/1,0/1,0/1}\)为 从高位向低位 \(DP\)到右起第\(x\)位，是否满足\(i<n\)，是否满足\(j<m\)，是否满足\((i\ xor\ j)>k\)的\(i\ xor\ j\)的末\(x\)位的总和，\(g_{x,0/1,0/1,0/1}\)表示对应的数的个数。

转移时，只要枚举\(i,j\)当前位置上填\(0\)还是\(1\)（注意，所填的数必须要符合大小限制，这一过程可以详见代码），然后转移。

最终的答案就是\(f_{lim,0,0,0}-kg_{lim,0,0,0}\)（\(lim\)为最高位）。

代码

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define LL long long
#define Inc(x,y) ((x+=(y))>=X&&(x-=X))
using namespace std;
LL N,M,K;int X;
class DigitalDP//数位DP
{
	private:
		#define SZ 70
		int lim,n[SZ+5],m[SZ+5],k[SZ+5];struct data {int v,t;}f[SZ+5][2][2][2];
		I void Init(LL x,int *v) {RI t=0;W(x) v[++t]=x&1,x>>=1;t>lim&&(lim=t);}
		I data DP(CI x,CI f1,CI f2,CI f3)
		{
			if(!x) return (data){0,f1&&f2&&f3};if(~f[x][f1][f2][f3].v) return f[x][f1][f2][f3];//边界&&记忆化
			data &F=f[x][f1][f2][f3],t;F.v=0;
			(f3||!k[x])&&(t=DP(x-1,f1|n[x],f2|m[x],f3),F.v=(t.v+F.v)%X,Inc(F.t,t.t));//填0,0
			(f1||n[x])&&(t=DP(x-1,f1,f2|m[x],f3|!k[x]),F.v=((1LL<<x-1)%X*t.t+t.v+F.v)%X,Inc(F.t,t.t));//填1,0
			(f2||m[x])&&(t=DP(x-1,f1|n[x],f2,f3|!k[x]),F.v=((1LL<<x-1)%X*t.t+t.v+F.v)%X,Inc(F.t,t.t));//填0,1
			(f1||n[x])&&(f2||m[x])&&(f3||!k[x])&&(t=DP(x-1,f1,f2,f3),F.v=(t.v+F.v)%X,Inc(F.t,t.t));//填1,1
			return f[x][f1][f2][f3];
		}
	public:
		I void Solve()
		{
			lim=0,Init(N,n),Init(M,m),Init(K,k);//转化为二进制
			RI i,x,y,z;for(i=1;i<=lim;++i) for(x=0;x^2;++x)//清空f
				for(y=0;y^2;++y) for(z=0;z^2;++z) f[i][x][y][z]=(data){-1,0};
			data res=DP(lim,0,0,0);printf("%d\n",(res.v-1LL*res.t*(K%X)%X+X)%X);//DP&&计算最终答案
			for(i=1;i<=lim;++i) n[i]=m[i]=k[i]=0;//注意这里的清空
		}
}D;
int main()
{
	RI Qt;scanf("%d",&Qt);W(Qt--) scanf("%lld%lld%lld%d",&N,&M,&K,&X),D.Solve();return 0;
}

【BZOJ4513】[SDOI2016] 储能表（数位DP）

原文：https://www.cnblogs.com/chenxiaoran666/p/BZOJ4513.html