[CF1518D] XOR Counting

XOR Counting
由于 a 可以为非负整数并且不关心 a 的具体数值,所以 m 大了后填很多 0 即可。
分类讨论。
m=1 时直接输出 n 即可。
m>=3 时,注意到 xor 运算与加运算同奇偶,所以 a 只能异或出来与 n 同奇偶的数。
可以构造出 \(a_1=x,a_2=\frac{n-x}{2},a_3=\frac{n-x}{2},a_4=0,a_5=0...\)
所以对于 x<=n 且与 n 同奇偶的数都可以异或出来,用等差数列求和即可。
m=2 时,相当于要求 x+y=n,x^y 的总和。
设 \(dp_{i,0/1}\) 从低到高表示当前在第 i 位,是否向下一位进位的 x^y 的总和,\(f_{i,/1}\) 表示方案数,因为对于每种 x^y 都需要判断是否加上 2^i。转移平凡。

#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int Mod=998244353;
const int Ni=(Mod+1)/2;
ll n,dp[62][2],f[62][2];int T,m;
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%lld%d",&n,&m);
		if(n==0){
			printf("0\n");continue;
		}
		if(m==1){printf("%lld\n",n%Mod);continue;}
		if(m>2){
			if(n%2==0){
				ll op=((n-2)%Mod*Ni%Mod+1ll)%Mod;printf("%lld\n",(2ll+n)%Mod*op%Mod*Ni%Mod);
			}
			else{
				ll op=((n-1)%Mod*Ni%Mod+1ll)%Mod;printf("%lld\n",(1ll+n)%Mod*op%Mod*Ni%Mod);
			}
			continue;
		}
		memset(dp,0,sizeof(dp));memset(f,0,sizeof(f));
		if(n&1){
			dp[0][0]=1;f[0][0]=1;
		}
		else{
			f[0][1]=1;f[0][0]=1;
		}
		for(int i=1;i<=60;i++){
			if((n&(1ll<<i))==0){
				dp[i][0]=dp[i-1][0];f[i][0]=f[i-1][0];
				dp[i][1]=dp[i-1][1];
				dp[i][1]=(((dp[i][1]+dp[i-1][0])%Mod)+f[i-1][1]*((1ll<<i)%Mod))%Mod;
				f[i][1]=(f[i-1][0]+f[i-1][1])%Mod;
			}
			else{
				dp[i][0]=dp[i-1][0];f[i][0]=f[i-1][0];
				dp[i][0]=((dp[i][0]+dp[i-1][1])%Mod)%Mod;
				dp[i][0]=(dp[i][0]+f[i-1][0]*((1ll<<i)%Mod))%Mod;
				dp[i][1]=dp[i-1][1];
				f[i][1]=f[i-1][1];
				f[i][0]=(f[i-1][0]+f[i-1][1]%Mod)%Mod;
			}
		}
		printf("%lld\n",dp[60][0]);
	}
	return 0;
}