Codeforces Round #822 (Div. 2) F. Zeros and Ones (Thue-Morse序列 & 带进位的数位dp)

题目

给定长无穷的Thue-Morse序列S，

t(t<=100)组询问，每次给定n,m(n,m<=1e18)，

询问串S0S1…Sm−1和串SnSn+1…Sn+m−1中不同的位数

思路来源

官方题解

Thue-Morse序列 - 知乎

题解

Thue-Morse这个序列有一些性质：

1. 其本质是在统计数字 i 的二进制 1 的个数的奇偶性（有奇数个1则 ai=1 ，有偶数个1则 ai=0 ）

2. 仅保留偶数项，仍与原数列相同；仅保留奇数项，即为原数列每项取反。

这里需要用到性质1，即统计[0,m)中有多少个数v满足v和v+n的二进制的奇偶性不同，

也就是[0,m)中有多少个数v满足v和v+n的二进制的1的数量和为奇数

然后就感觉和这个题很像啊，都是需要开一维暂存当前前缀可能对将来的影响，

Educational Codeforces Round 104 (Rated for Div. 2) F.Ones(数位dp)_Code92007的博客-CSDN博客

姑且称为带进位的数位dp了

dp[i][j][k(0/1)][l(0/1)]表示当前在从高到低第i位，

v+n（只考虑i及更高位）的当前尾随1有j个，

v和v+n（只考虑i及更高位）的二进制表示中1的个数和是否为奇数（0/1），

当前x的值卡不卡m的上界（0/1）的方案数

其实就是为了消除后效性，考虑要加入哪些维度

转移考虑，在v的第x位取0/1时，v+n会不会进位，

v和(v+n)的二进制中1的个数的奇偶性会如何变化

如果进位，则v+n之前trail个1变为一个1，减少了trail-1个，one需要作对应异或

v这位取0/1，one也需要做对应异或

这样单次询问复杂度是O((logn)^2)的，其实就是dp数组的大小

代码1 O((logn)^2)

#include
using namespace std;
typedef long long ll;
int t;
ll n,m,dp[64][65][2][2];
ll dfs(int x,int trail,bool one,bool lim){
	if(x==-1){
		return one==1 && !lim;
	}
	if(~dp[x][trail][one][lim])return dp[x][trail][one][lim];
	ll &ans=dp[x][trail][one][lim];ans=0;
	int bit=n>>x&1,up=lim?(m>>x&1):1;
	for(int i=0;i<=up;++i){
		int w=bit+i;
		if(!w)ans+=dfs(x-1,0,one,lim && (i==up));
		else if(w==1)ans+=dfs(x-1,trail+1,one^1^i,lim && (i==up));
		else if(w==2)ans+=dfs(x-1,0,one^((trail-1)&1)^1,lim && (i==up));
	}
	//printf("dp[%d][%d][%1d][%1d]:%lld\n",x,trail,one,lim,dp[x][trail][one][lim]);
	return ans;
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%lld%lld",&n,&m);
		memset(dp,-1,sizeof dp);
		printf("%lld\n",dfs(63,0,0,1));
	}
	return 0;
}

代码2 O(logn)

注意到转移中只会用到trail+1和trail-1，所以trail没有必要开64，开2表示当前奇偶性就可以了

#include
using namespace std;
typedef long long ll;
int t;
ll n,m,dp[64][2][2][2];
ll dfs(int x,int trail,bool one,bool lim){
	if(x==-1){
		return one==1 && !lim;
	}
	if(~dp[x][trail][one][lim])return dp[x][trail][one][lim];
	ll &ans=dp[x][trail][one][lim];ans=0;
	int bit=n>>x&1,up=lim?(m>>x&1):1;
	for(int i=0;i<=up;++i){
		int w=bit+i;
		if(!w)ans+=dfs(x-1,0,one,lim && (i==up));
		else if(w==1)ans+=dfs(x-1,trail^1,one^1^i,lim && (i==up));
		else if(w==2)ans+=dfs(x-1,0,one^trail,lim && (i==up));
	}
	return ans;
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%lld%lld",&n,&m);
		memset(dp,-1,sizeof dp);
		printf("%lld\n",dfs(63,0,0,1));
	}
	return 0;
}

Todo

F题还看到有另一种做法，待补

Codeforces Round #822 (Div. 2) EF_枉玊的博客-CSDN博客