BZOJ 4513 储能表

发表于 | 更新于

Link

真的很想自己做出来，于是就想按套路先DP预处理再用输入去卡DP值。。 然而真的想不出来。 所以套路要有，但只会套路做题也是不行的。

Tips

数位DP可以边DP边卡上下界×2\times 2。 只要在状态里设计上需不需要继续卡边界即可×2\times 2

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include "lucida"
const int MAXB=70;
int64 f[MAXB][2][2][2],g[MAXB][2][2][2];
//f个数					g总和
int64 Solve(int64 n,int64 m,int64 K,int P) {
	memset(f,0,sizeof(f));
	memset(g,0,sizeof(g));
	f[64][1][1][1]=1;
	--n;--m;
	for(int i=63;~i;--i) {
		int bn=n>>i&1;
		int bm=m>>i&1;
		int bk=K>>i&1;//bn^bm;
		for(int fns=0;fns<2;++fns)
			for(int fms=0;fms<2;++fms)
				for(int fks=0;fks<2;++fks)
					for(int newn=0;newn<2;++newn)
						for(int newm=0;newm<2;++newm) {
							int newk=newn^newm;
							if((fns && newn>bn) || (fms && newm>bm) || (fks && newk<bk)) continue;
							int gns=fns && (newn==bn),
								gms=fms && (newm==bm),
								gks=fks && (newk==bk);
							(f[i][gns][gms][gks]+=f[i+1][fns][fms][fks])%=P;
							(g[i][gns][gms][gks]+=(g[i+1][fns][fms][fks]+(f[i+1][fns][fms][fks]*(((int64)newk<<i)%P))%P))%=P;
						}
	}
	int64 Ans=0;K%=P;
	for(int ns=0;ns<2;++ns)
		for(int ms=0;ms<2;++ms)
			for(int ks=0;ks<2;++ks)
				(Ans+=g[0][ns][ms][ks]-K*f[0][ns][ms][ks])%=P;
	return (Ans+P)%P;
}
int main() {
	freopen("input","r",stdin);
	int T;is>>T;
	while(T--) {
		int64 n,m,K;
		int P;
		is>>n>>m>>K>>P;
		os<<Solve(n,m,K,P)<<'\n';
	}
	return 0;
}