自动搬运

查看原文

来自洛谷，原作者为

	lytqwq ..

搬运于2025-08-24 21:56:07，当前版本为作者最后更新于2021-01-18 08:07:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这题对初学数位DP的我很不友好

洛谷上的第一个题解没写明白状态。百度到的其他的题解也大多是 “直接DP就好了” “只写了状态” “看我代码” ，或者没说该怎么样数位DP

在翻了12页百度后， 有了这篇题解...

题目要我们求这个东西：

$$\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} \mathrm{max} ((i \mathrm{xor} j)-k,0) $$

我们可以把问题分成 求异或值大于$k$的对数 $S1$ ，异或值大于$k$的异或和 $S2$

答案就变为了 $S2-S1\times k$

至于怎么求，数位DP

定义

$f_{i,a,b,c}$ $i$ ：考虑到第 $i$ 位， $a,b,c$ 为 $1$ 时表示 前面到第 $i$ 位分别和 $n,m,k$ 的前面到第 $i$ 位相等时的异或和 为 $0$ 时表示 $i$ 位分别比 $n,m$ 的前面到第 $i$ 位小和比 $k$ 的前面到第 $i$ 位大时的异或和

$f$ 的异或和要去掉 前面到第 $i$ 位的 $k$

$g_{i,a,b,c}$ 同上，但是表示是对数

转移在注释上

#include<bits/stdc++.h>
using namespace std;
const long long int N=70;
long long int f[N][2][2][2],g[N][2][2][2];
// f_{i,a,b,c} i：考虑到第i位， a,b,c 为1时表示 前面到第i位分别和n,m,k的前面到第i位相等时的异或和 为0时表示i位分别比n,m的前面到第i位小和比k的前面到第i位大时的异或和 
//f已经去掉 前面到第i位的k 
//g_{i,a,b,c} 同上，但是表示对数 
long long int n,m,k,T,p;
int main(){
	scanf("%lld",&T);
	while(T--){
		memset(f,0,sizeof(f));
		memset(g,0,sizeof(g));
		scanf("%lld%lld%lld%lld",&n,&m,&k,&p);
		g[62][1][1][1]=1;
		for(int i=61;i>=1;i--){//从高位往低位推 
			long long int x=(n>>(i-1))&1,y=(m>>(i-1))&1,z=(k>>(i-1))&1;// x: n在第i位的数； y:m在第i位的数；z：k在第i位的数 
			for(long long int a=0;a<2;a++){ //是不是前面到第i位和n的相等
				for(long long int b=0;b<2;b++){//是不是前面到第i位和m的相等
					for(long long int c=0;c<2;c++){//是不是前面到第i位和k的相等
						if(f[i+1][a][b][c] || g[i+1][a][b][c]){//此处是刷表法，从i,a,b,c转移出去 
							for(long long int xx=0;xx<2;xx++){//转移到第i位的数 是 
								for(long long int yy=0;yy<2;yy++){//转移到第i位的数 是 
									long long int zz=xx^yy;// 已知了这一位的数，这一位的异或就知道了 
									if((a && x<xx)||(b && y<yy)||(c && z>zz)){ 
										continue;
										//1.不能让 前面到第i位相等，现在还这一位比n的这一位大
										//2.不能让 前面到第i位相等，现在还这一位比m的这一位大
										//3.不能让 前面到第i位相等，现在还这一位比k的这一位小 
									}
									long long int aa=(a && x==xx),bb=(b && y==yy),cc=(c && z==zz);
									//如果前面到第i位都相等，现在这一位也相等，就是1，需要再看后面的数才能判断大小 
									//不然就为0，意为在必定在限制之内 
									//可以发现不会从0转移到1，只会从1转移到0 
									g[i][aa][bb][cc]+=g[i+1][a][b][c];
									//转移 g
									g[i][aa][bb][cc]%=p;
									f[i][aa][bb][cc]+=f[i+1][a][b][c]+(zz-z+p)%p*((1ll<<(i-1))%p)%p*g[i+1][a][b][c]%p;
									//转移 f，后一项中的(zz-z+p)%p*((1ll<<(i-1))%p)%p就是转移的数的每一位都去掉k的那一位后这一位的贡献， g[i+1][a][b][c]为转移的数量 
									f[i][aa][bb][cc]%=p;
								}
							}
						}
					}
				}
			}
		}
		printf("%lld\n",f[1][0][0][0]);
		//考虑完最后一位,注意到是0~(n-1)和0~(m-1)，所以直接用表示小于n,m的0，当 两个数异或为k的时候，都减了k，就没必要算了，直接算让异或值大于k 
	}
}