【T5异或】【求调】

charlieqi · 2025 年6 月 1 日 03:17

#include<bits/stdc++.h>
#define int long long
const int maxn=70;
using namespace std;
int T,n,m,k,p;
int dp[maxn][2][2][2],f[maxn][2][2][2];
signed main(){
	cin>>T;
	while(T--){
		memset(dp,0,sizeof(dp));
		memset(f,0,sizeof(f));
		f[62][1][1][1]=1;
		cin>>n>>m>>k>>p;
		for(int i=61;i>=1;i--){
			int x=n&(1<<(i-1));
			int y=m&(1<<(i-1));
			int z=k&(1<<(i-1));
			for(int a=0;a<=1;a++){
				for(int b=0;b<=1;b++){
					for(int c=0;c<=1;c++){
						if(dp[i+1][a][b][c]){
							for(int xx=0;xx<=1;xx++){
								for(int yy=0;yy<=1;yy++){
									int zz=xx^yy;
									if((a&&xx>x)||(b&&yy>y)||(c&&zz<z)){
										continue;
									}
									int aa=(a&&x==xx);
									int bb=(b&&y==yy);
									int cc=(c&&z==zz);
									f[i][aa][bb][cc]=(f[i][aa][bb][cc]+f[i+1][a][b][c])%p;
									dp[i][aa][bb][cc]=(dp[i][aa][bb][cc]+dp[i+1][a][b][c]*((zz-z+p)%p*(1<<(i-1))%p)%p)%p;
								}
							}
						}
					}
				}
			}
		}
		cout<<dp[1][0][0][0]%p<<"\n";
	}
	return 0;
}

王峥睿 · 2025 年6 月 1 日 03:17

dp[i][aa][bb][cc]=(dp[i][aa][bb][cc]+dp[i+1][a][b][c]((zz-z+p)%p(1<<(i-1))%p)%p)%p;
dp[i][aa][bb][cc]=(dp[i][aa][bb][cc]+f[i+1][a][b][c]((zz-z+p)%p(1<<(i-1))%p)%p)%p;
改成f。因为ans要+当前位次数*每次贡献,所以f->当前位次数,因此你要改成f

王峥睿 · 2025 年6 月 1 日 03:17

上一句改成下一句

王峥睿 · 2025 年6 月 1 日 03:18

int T,n,m,k,p;
你这直接见祖宗了

charlieqi · 2025 年6 月 1 日 03:19

可能是判断语句的问题？

#include<bits/stdc++.h>
#define int long long
const int maxn=70;
using namespace std;
int T,n,m,k,p;
int dp[maxn][2][2][2],f[maxn][2][2][2];
signed main(){
	cin>>T;
	while(T--){
		memset(dp,0,sizeof(dp));
		memset(f,0,sizeof(f));
		f[62][1][1][1]=1;
		cin>>n>>m>>k>>p;
		for(int i=61;i>=1;i--){
			int x=n&(1<<(i-1));
			int y=m&(1<<(i-1));
			int z=k&(1<<(i-1));
			for(int a=0;a<=1;a++){
				for(int b=0;b<=1;b++){
					for(int c=0;c<=1;c++){
						if(dp[i+1][a][b][c]){
							for(int xx=0;xx<=1;xx++){
								for(int yy=0;yy<=1;yy++){
									int zz=xx^yy;
									if((a&&xx>x)||(b&&yy>y)||(c&&zz<z)){
										continue;
									}
									int aa=(a&&x==xx);
									int bb=(b&&y==yy);
									int cc=(c&&z==zz);
									f[i][aa][bb][cc]=(f[i][aa][bb][cc]+f[i+1][a][b][c])%p;
									dp[i][aa][bb][cc]=(dp[i][aa][bb][cc]+f[i+1][a][b][c]*((zz-z+p)%p*(1<<(i-1))%p)%p)%p;
								}
							}
						}
					}
				}
			}
		}
		cout<<dp[1][0][0][0]%p<<"\n";
	}
	return 0;
}

王峥睿 · 2025 年6 月 1 日 03:20

nmk一定要开longlong，我没开连样例都过不了,开了就过阳历了

王峥睿 · 2025 年6 月 1 日 03:20

dp和f都不开longlong，乘的时候不就全爆了吗
最好全开上long long

王峥睿 · 2025 年6 月 1 日 03:21

if(dp[i+1][a][b][c])
改成(dp[i+1][a][b][c]||f[i+1][a][b][c])

charlieqi · 2025 年6 月 1 日 03:23

没有用：

#include<bits/stdc++.h>
#define int long long
const int maxn=70;
using namespace std;
int T,n,m,k,p;
int dp[maxn][2][2][2],f[maxn][2][2][2];
signed main(){
	cin>>T;
	while(T--){
		memset(dp,0,sizeof(dp));
		memset(f,0,sizeof(f));
		f[62][1][1][1]=1;
		cin>>n>>m>>k>>p;
		for(int i=61;i>=1;i--){
			int x=n&(1<<(i-1));
			int y=m&(1<<(i-1));
			int z=k&(1<<(i-1));
			for(int a=0;a<=1;a++){
				for(int b=0;b<=1;b++){
					for(int c=0;c<=1;c++){
						if(f[i+1][a][b][c]){
							for(int xx=0;xx<=1;xx++){
								for(int yy=0;yy<=1;yy++){
									int zz=xx^yy;
									if((a&&xx>x)||(b&&yy>y)||(c&&zz<z)){
										continue;
									}
									int aa=(a&&x==xx);
									int bb=(b&&y==yy);
									int cc=(c&&z==zz);
									f[i][aa][bb][cc]=(f[i][aa][bb][cc]+f[i+1][a][b][c])%p;
									dp[i][aa][bb][cc]=(dp[i][aa][bb][cc]+f[i+1][a][b][c]*((zz-z+p)%p*(1<<(i-1))%p)%p)%p;
								}
							}
						}
					}
				}
			}
		}
		cout<<dp[1][0][0][0]%p<<"\n";
	}
	return 0;
}

椰子糕 · 2025 年6 月 1 日 03:24

总和更新的逻辑还没对 ,
dp[i][aa][bb][cc] = 自身 + 高位的贡献 + 当前位的贡献(需要f数组参与)

椰子糕 · 2025 年6 月 1 日 03:27

当前位的贡献应该是 : 有效数量 * 当前位i⊕j和k的差值 * 位权

charlieqi · 2025 年6 月 1 日 03:27

#include<bits/stdc++.h>
#define int long long
const int maxn=70;
using namespace std;
int T,n,m,k,p;
int dp[maxn][2][2][2],f[maxn][2][2][2];
signed main(){
	cin>>T;
	while(T--){
		memset(dp,0,sizeof(dp));
		memset(f,0,sizeof(f));
		f[62][1][1][1]=1;
		cin>>n>>m>>k>>p;
		for(int i=61;i>=1;i--){
			int x=n&(1<<(i-1));
			int y=m&(1<<(i-1));
			int z=k&(1<<(i-1));
			for(int a=0;a<=1;a++){
				for(int b=0;b<=1;b++){
					for(int c=0;c<=1;c++){
						if(f[i+1][a][b][c]||dp[i+1][a][b][c]){
							for(int xx=0;xx<=1;xx++){
								for(int yy=0;yy<=1;yy++){
									int zz=xx^yy;
									if((a&&xx>x)||(b&&yy>y)||(c&&zz<z)){
										continue;
									}
									int aa=(a&&x==xx);
									int bb=(b&&y==yy);
									int cc=(c&&z==zz);
									f[i][aa][bb][cc]=(f[i][aa][bb][cc]+f[i+1][a][b][c])%p;
									dp[i][aa][bb][cc]=(dp[i][aa][bb][cc]+dp[i+1][a][b][c]+f[i+1][a][b][c]*((zz-z+p)%p*(1<<(i-1))%p)%p)%p;
								}
							}
						}
					}
				}
			}
		}
		cout<<dp[1][0][0][0]%p<<"\n";
	}
	return 0;
}

王峥睿 · 2025 年6 月 1 日 03:28

			int x=n&(1<<(i-1));
			int y=m&(1<<(i-1));
			int z=k&(1<<(i-1));

改成

			int x=(n>>(i-1))&1;
			int y=(m>>(i-1))&1;
			int z=(k>>(i-1))&1;

dp[i][aa][bb][cc]=(dp[i][aa][bb][cc]+dp[i+1][a][b][c]+f[i+1][a][b][c]((zz-z+p)%p(1<<(i-1))%p)%p)%p;
你这里都写左移了前面不能这么写

王峥睿 · 2025 年6 月 1 日 03:30

要么就改dp状态转移

charlieqi · 2025 年6 月 1 日 03:30

不一样吗？

王峥睿 · 2025 年6 月 1 日 03:32

还有,老师,

1<<(i-1)

要改成

1ll<<(i-1)

要不然1<<60直接见祖宗

王峥睿 · 2025 年6 月 1 日 03:36

如果按你上面那样写
设n=1101（二进制）
在i=3（十进制）时,x=100（二进制）
下面你又<<2位,到第四位了，很明显是错的
而按我的写
设n=1101（二进制）
在i=3（十进制）时,x=1（二进制）
下面<<2位,与原来位数相符

charlieqi · 2025 年6 月 1 日 03:39

60了

#include<bits/stdc++.h>
typedef long long ll;
const int maxn=70;
using namespace std;
ll T,n,m,k,p;
ll dp[maxn][2][2][2],f[maxn][2][2][2];
signed main(){
	cin>>T;
	while(T--){
		memset(dp,0,sizeof(dp));
		memset(f,0,sizeof(f));
		f[62][1][1][1]=1;
		cin>>n>>m>>k>>p;
		for(int i=61;i>=1;i--){
			ll x=(n>>(i-1))&1ll;
			ll y=(m>>(i-1))&1ll;
			ll z=(k>>(i-1))&1ll;
			for(int a=0;a<=1;a++){
				for(int b=0;b<=1;b++){
					for(int c=0;c<=1;c++){
						if(f[i+1][a][b][c]){
							for(int xx=0;xx<=1;xx++){
								for(int yy=0;yy<=1;yy++){
									ll zz=xx^yy;
									if((a&&xx>x)||(b&&yy>y)||(c&&zz<z)){
										continue;
									}
									ll aa=(a&&x==xx);
									ll bb=(b&&y==yy);
									ll cc=(c&&z==zz);
									f[i][aa][bb][cc]=(f[i][aa][bb][cc]+f[i+1][a][b][c])%p;
									dp[i][aa][bb][cc]=(dp[i][aa][bb][cc]+dp[i+1][a][b][c]+f[i+1][a][b][c]*((zz-z+p)%p*(1ll<<(i-1))%p)%p)%p;
								}
							}
						}
					}
				}
			}
		}
		cout<<dp[1][0][0][0]%p<<"\n";
	}
	return 0;
}

王峥睿 · 2025 年6 月 1 日 03:41

（帖子已被作者删除）

王峥睿 · 2025 年6 月 1 日 03:48

//这代码是我用来帮别人测试的,管理通融一下 
#include<bits/stdc++.h>
typedef long long ll;
const int maxn=70;
using namespace std;
ll T,n,m,k,p;
ll dp[maxn][2][2][2],f[maxn][2][2][2];
signed main(){
	cin>>T;
	while(T--){
		memset(dp,0,sizeof(dp));
		memset(f,0,sizeof(f));
		f[62][1][1][1]=1;
		cin>>n>>m>>k>>p;
		for(long long i=61;i>=1;i--){
			ll x=(n>>(i-1))&1ll;
			ll y=(m>>(i-1))&1ll;
			ll z=(k>>(i-1))&1ll;
			for(long long a=0;a<=1;a++){
				for(long long b=0;b<=1;b++){
					for(long long c=0;c<=1;c++){
						if(f[i+1][a][b][c]){
							for(long long xx=0;xx<=1;xx++){
								for(long long yy=0;yy<=1;yy++){
									ll zz=xx^yy;
									if((a&&xx>x)||(b&&yy>y)||(c&&zz<z)){
										continue;
									}
									ll aa=(a&&x==xx);
									ll bb=(b&&y==yy);
									ll cc=(c&&z==zz);
									f[i][aa][bb][cc]=(f[i][aa][bb][cc]+f[i+1][a][b][c])%p;
									dp[i][aa][bb][cc]=(dp[i][aa][bb][cc]+dp[i+1][a][b][c]+(f[i+1][a][b][c]*((((zz-z+p)%p)*((1ll<<i-1)%p))%p))%p)%p;
								}
							}
						}
					}
				}
			}
		}
		cout<<dp[1][0][0][0]%p<<"\n";
	}
	return 0;
}