BZOJ 4513 储能表

Link

真的很想自己做出来,于是就想按套路先DP预处理再用输入去卡DP值。。 然而真的想不出来。 所以套路要有,但只会套路做题也是不行的。 # Tips 数位DP可以边DP边卡上下界\(\times 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;
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2017 Hey,Lucida here. All Rights Reserved.

Lucida Lu 保留所有权利