sdoi2016 储能表
很好的计数型数位dp，刷表法，一维表示阶段，半维限制范围，dp过程不断进行可行性剪枝
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
usingnamespacestd;
llt,n,m,k,p,ans,f[100][2][2][2],g[100][2][2][2],bin[100];
inlinellread()
{
llx=0,f=1;charch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
returnx*f;
}
intmain()
{
t=read();
while(t--)
{
n=read()-1;m=read()-1;k=read();p=read();
bin[0]=1;F(i,1,60)bin[i]=bin[i-1]*2%p;
ans=0;
memset(f,0,sizeof(f));memset(g,0,sizeof(g));
f[0][1][1][1]=1;
F(i,0,60)F(a,0,1)F(b,0,1)F(c,0,1)if(f[i][a][b][c])
{
lltn=n&(1ll<<(60-i))?1:0,tm=m&(1ll<<(60-i))?1:0,tk=k&(1ll<<(60-i))?1:0;
F(x,0,1)if(!a||x<=tn)F(y,0,1)if(!b||y<=tm)
{
intz=x^y;
if(c&&z<tk)continue;
intta=(a&&x==tn)?1:0,tb=(b&&y==tm)?1:0,tc=(c&&z==tk)?1:0;
(f[i+1][ta][tb][tc]+=f[i][a][b][c])%=p;
(g[i+1][ta][tb][tc]+=g[i][a][b][c])%=p;
if(z)(g[i+1][ta][tb][tc]+=bin[60-i]*f[i][a][b][c]%p)%=p;
}
}
F(a,0,1)F(b,0,1)F(c,0,1)ans=((ans+g[61][a][b][c]-k%p*f[61][a][b][c]%p)%p+p)%p;
printf("%lld\n",ans);
}
return0;
}
评论