自动搬运

查看原文

来自洛谷，原作者为

	EternalAlexander 魔力的碎片都不再拥有的少年

搬运于2025-08-24 22:10:15，当前版本为作者最后更新于2020-04-30 18:19:16，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

怎么没有题解，水一个。

考虑怎么算 $SG(x)$ 。我们断言 $SG(2^k+n) = n+1 (n\in[0,2^k))$。

假设上述结论对所有 $i<x$ 都成立，我们证明该结论对 $x=2^k+n$ 成立。

若 $x=2^k$ ，$SG(x)=1$。如果 $y$ 的第 $k$ 位为 $1$，则只能 $y=x$，否则如果不为 $1$，则 $y \bigoplus x > x$。综上 $x$ 的后继状态只有 $0$，故 $SG(x)=1$。

对于 $x = 2^k + n, n \in [0,2^k)$，$SG(x) = n$ 。依然考虑最高位，如果为 $0$ 则 $x \bigoplus y \in [2^k, 2^k+n)$，显然这些后继的 $SG$ 值包含了 $[1,n]$。注意到 $0$ 也是 $x$ 的后继，因此 $[0,n]$ 都出现过。

否则，设去掉最高位的 $y$ 为 $y'$ ，有 $y' \leq n$ 且 $x \bigoplus y = n \bigoplus y'$。设 $m=2^{\lfloor \log_2 n \rfloor}$，显然有 $SG(n \bigoplus y') \leq m \leq n$。

综上，$x$ 后继的 $SG$ 值的 $\operatorname{mex}$ 为 $n+1$，则 $SG(x)=n+1$。

至此我们可以在 $O(m \log m)$ 的时间内算出 $[1,m]$ 的 $SG$ 值，就是要选出 $|V|$ 个数使得它们的 $SG$ 值的异或和不为 $0$。

设 $A_i = \sum_{x=1}^m [SG(x)=i]$，$B=A^{|V|}$（这里的乘法是异或卷积运算），则选取 $|V|$ 个数使得异或和为 $x$ 的方案数即为 $B_x$。

那么现在的问题就是怎么做异或卷积快速幂，每次 FWT 一遍复杂度不太对，我们可以先 FWT 一次，然后用 FWT 后的数组做乘法，最后 FWT 回来，就可以做到 $O(m \log |V|)$ 了。

至此我们在 $O(m \log m + m \log |V|)$ 的时间内解决了这个简单的问题。

#include <bits/stdc++.h>
#define maxn 1048576
#define ll long long
const int mod=998244353;
const int inv2=(mod+1)/2;
int A[maxn],b[maxn],n,lim;
ll k;

int SG(int x){
	int len=1,sum=0;
	while(sum<x){
		sum+=len;
		if(sum>=x)return x-(sum-len);
		len<<=1;
	}
}

void FWT(int *a,int lim,int flag){
	for(int i=1;i<lim;i<<=1)
	for(int j=0;j<lim;j+=(i<<1))
	for(int k=0;k<i;++k){
		int a1=a[j+k],a2=a[j+k+i];
		a[j+k]=(a1+a2)%mod;a[j+k+i]=(a1-a2+mod)%mod;
		if(flag==-1){
			a[j+k]=(ll)a[j+k]*inv2%mod;a[j+k+i]=(ll)a[j+k+i]*inv2%mod;
		}
	}
}

void mul(int *a,int *b,int lim){
	for(int i=0;i<lim;++i)a[i]=(ll)a[i]*b[i]%mod;
}

void qpow(int *a,ll k,int lim){
	b[0]=1;FWT(b,lim,1);
	while(k){
		if(k&1)mul(b,a,lim);
		mul(a,a,lim);
		k>>=1;
	}std::memcpy(a,b,sizeof(b));
}

int main(){
	int max=0;lim=1;
	scanf("%lld%d",&k,&n);
	for(int i=1;i<=n;++i){
		int d=SG(i);
		A[d]++;
		max=std::max(max,d);
	}while(lim<=max)lim<<=1;
	FWT(A,lim,1);
	qpow(A,k,lim);
	FWT(A,lim,-1);
	int sum=0;
	for(int i=1;i<lim;++i)sum=(sum+A[i])%mod;
	printf("%d",sum);
	return 0;
}