文件详细信息

下载本文件

本文件的大小为 1931 字节。

#include<cstdio>
#include<cstring>
typedef long long ll;
ll read(){
	int ch=getchar();
	ll num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
	return num;
}
const int maxn=65;
int T;
ll n,m,k,p;
int pow[maxn],f[maxn][8],g[maxn][8];//将 a,b,c 三维压到 j 一维
//注意：对于数组 f 和 g，为了防止第一维的值为 -1，将题解中的 f[i][a][b][c] 表示成 f[i+1][a][b][c]
int main(){
	register int i,j,x,y,a,b,c,nj;
	T=read();
	while(T--){
		n=read(),m=read(),k=read(),p=read();
		pow[0]=1%p;
		for(i=1;i<=61;i++)pow[i]=(pow[i-1]<<1)%p;
		memset(f,0,sizeof(f));
		memset(g,0,sizeof(g));
		//本题可以用记忆化搜索，这里使用 DP 来模拟搜索时的回溯过程
		f[0][0]=1%p;//边界状态
		for(i=0;i<=60;i++)
			for(j=0;j<8;j++)//为减少 for 循环的层数，使用 j 来表示 a,b,c
				for(x=0;x<2;x++)//x 表示数字 i 这一位是 0 还是 1
					for(y=0;y<2;y++){//y 表示数字 j 这一位是 0 还是 1
						a=j&1,b=(j>>1)&1,c=(j>>2)&1;
						if((a==1&&x>((n>>i)&1))||(b==1&&y>((m>>i)&1))||(c==1&&(x^y)<((k>>i)&1)))continue;
						//当前数顶了 n 的上界，n 的第 i 位时 0，而当前数的第 i 位是 1，超过了 n，排除
						//当前数顶了 m 的上界，m 的第 i 位是 0，而当前数的第 i 位是 1，超过了 m，排除
						//当前数顶了 k 的上界，k 的第 i 位是 1，而当前数的第 i 位是 0，没超过 k，排除
						//否则 f[i][j] 可以从 f[i][nj] 转移过来
						a=a&&x==((n>>i)&1),b=b&&y==((m>>i)&1),c=c&&(x^y)==((k>>i)&1),nj=a|(b<<1)|(c<<2);
						//如果当前数没有真正的顶到 n/m/k（即 n/m/k 的第 i 位与当前数的第 i 位不相等），则记作没有顶到
						f[i+1][j]=(f[i+1][j]+f[i][nj])%p;
						g[i+1][j]=(g[i+1][j]+g[i][nj]+(ll)(x^y)*f[i][nj]*pow[i]%p)%p;
					}
		printf("%lld\n",(g[61][7]-(ll)f[61][7]*(k%p)%p+p)%p);
	}
	return 0;
}