bzoj4513 [Sdoi2016]儲能表 dp

這種數位dp第一次見。。

其實應該是利用位運算互相獨立來避免後效性

一般的數位dp隻有一個範圍 這個題有三個範圍。。

由于數位和整個數的大小沒直接關系，是以就需要用狀态記錄

首先不合法的一定不轉移，對于n和m的限制 ，一位合法的話有可能出現後面無論如何都合法， 與後面的數不能小于剩下的數，由于比他大的都不合法了，是以剩下的一定是與n、m前面幾位相同的

是以就設計狀态1表示前面幾位都與n/m/k相同  0表示不同且合法（即後面的就都合法了）

比較暴力的dp。

注意%p的時候k本身要%p。。

碼：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
ll er[76],n,m,ans,K,p,f[76][2][2][2],i1,i2,g[76][2][2][2];
int T,i,j,k,l;
int main()
{
	er[0]=1;
	for(i=1;i<=63;i++)
	er[i]=er[i-1]*2;
	scanf("%d",&T);
	while(T--)
	{ans=0;
	memset(f,0,sizeof(f));
	memset(g,0,sizeof(g));
	scanf("%lld",&n);
	n--;
	scanf("%lld",&m);
	m--;
	scanf("%lld",&K);	
	scanf("%lld",&p);	
	f[63][1][1][1]=1;	
	for(i=62;i>=0;i--)
	{
	for(j=0;j<=1;j++)
	for(k=0;k<=1;k++)
	for(l=0;l<=1;l++)
	{
		for(i1=0;i1<=1;i1++)
		for(i2=0;i2<=1;i2++)
		{
			int mbj,mbk,mbl;			
			if(j==1&&(!(n&er[i]))&&i1)	continue; //是0  
			if(k==1&&(!(m&er[i]))&&i2)	continue;   //是0
		 	if(l==1&&(K&er[i])&&(!(i1^i2)))continue;  //是1  
		    if(j==1&&(!(n&er[i]))&&(!i1))mbj=1;
		    if(k==1&&(!(m&er[i]))&&(!i2))mbk=1;
		    if(l==1&&(!(K&er[i]))&&(!(i1^i2)))mbl=1;
			if(j==1&&(n&er[i])&&i1)mbj=1;
			if(k==1&&(m&er[i])&&i2)mbk=1;	
			if(l==1&&(K&er[i])&&(i1^i2))mbl=1;
			if(j==1&&(n&er[i])&&(!i1))mbj=0;
			if(k==1&&(m&er[i])&&(!i2))mbk=0;				  
			if(l==1&&(!(K&er[i]))&&(i1^i2))mbl=0; 
			if(j==0)mbj=0;
			if(k==0)mbk=0;
			if(l==0)mbl=0;
			f[i][mbj][mbk][mbl]+=f[i+1][j][k][l];
			f[i][mbj][mbk][mbl]%=p;
			g[i][mbj][mbk][mbl]+=((i1^i2)*er[i]%p*f[i+1][j][k][l]%p+g[i+1][j][k][l])%p;
			g[i][mbj][mbk][mbl]%=p;
		}	
	}
	}
for(i=0;i<=1;i++)for(j=0;j<=1;j++)for(k=0;k<=1;k++)ans-=(f[0][i][j][k]*(K%p))%p,ans%=p,     ans+=g[0][i][j][k],ans%=p;  
printf("%lld\n",(ans+p)%p);
    }
}