SDOI2016储能表

数位DP，枚举转移

(f[i][1/0][1/0][1/0])表示前(i)位，(x)前(i)位卡满/比(n)的前(i)位小，(y)前(i)位卡满/比(m)的前(i)为小，异或后前(i)位卡满/比(k)的前(i)为大的总分数，(g[i][1/0][1/0][1/0])同理表示方案数（也有可能是第，我也不是很清楚）

(ans=f[0][0][0][0])

即可枚举转移

#include<bits/stdc++.h>
using namespace std;
#define int long long 
inline int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f==1?x:-x;
}
int n,m,k,mod,f[64][2][2][2],g[64][2][2][2]; 
signed main(){
	int T=read();
	while(T--){
		memset(f,0,sizeof(f));
		memset(g,0,sizeof(g));
		n=read();m=read();k=read();mod=read();
		g[61][1][1][1]=1;
		for(int i=60,in,im,ik,w,aa,bb,cc;i>=0;i--){
			in=(n>>i)&1;im=(m>>i)&1;ik=(k>>i)&1;
			for(int a=0;a^2;a++)for(int b=0;b^2;b++)for(int c=0;c^2;c++){//枚举转移状态 
				if(!f[i+1][a][b][c]&&!g[i+1][a][b][c])continue;
				for(int u=0;u^2;u++)for(int v=0;v^2;v++){//枚举第i位的值 
					w=u^v;
					if((a&&in<u)||(b&&im<v)||(c&&ik>w))continue;
					aa=(a&&in==u);bb=(b&im==v);cc=(c&&ik==w);
					g[i][aa][bb][cc]=(g[i][aa][bb][cc]+g[i+1][a][b][c])%mod;
					f[i][aa][bb][cc]=(((w-ik+mod)%mod)*((1ll<<i)%mod)%mod*g[i+1][a][b][c]%mod+f[i][aa][bb][cc]+f[i+1][a][b][c])%mod;
				}
			}
		}
		cout<<f[0][0][0][0]<<"
";
	}
	return (0-0);
}