自动搬运

查看原文

来自洛谷，原作者为

	Time_tears oi复健ing

搬运于2025-08-24 22:31:30，当前版本为作者最后更新于2021-06-13 15:54:34，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

Nim游戏先手必胜当且仅当所有石子的 Xor 非 0。

也就是说我们要求的是：把n个石子分成m堆，每堆不超过上限且 Xor 非 0 的方案数

而这个东西不太好求，可以转换为求：总方案数-每堆不超过上限且 Xor 为 0 的方案数

总方案数：

$$\sum\limits_{S}(-1)^{|S|}\times\binom{n-\sum_{i\in S}(a_i+1)+m-1}{m-1} $$

直接 $2^m$ 枚举子集即可。

考虑怎么求堆不超过上限且 Xor 为 0 的方案数，容易想到数位 Dp，只不过我们现在需要把 $m$ 堆是否顶着上限都要压入状态中。

所以设：$f_{i,s,j}$ 表示从高到低 Dp 到第 $i$ 位，目前被卡上界的集合是 $s$，低位向这一位进位 $j$ 次，注意 $j$ 的范围只能是 $0\to m-1$。

考虑直接枚举每一个数在这一位填 $0/1$，复杂度约为 $O(4^mm\log n)$，应该无法通过。

注意到我们只需要枚举目前还顶着上界的，没顶着上界的只需要枚举有几个 $1$ 再乘上组合数即可，这样复杂度就降为了 $O(3^mm^2\log n)$，代码颇多细节。

#include<bits/stdc++.h>
#define N 11
#define ll long long
using namespace std;
const int mod=998244353;
ll n,a[N];
int m,S,c[N][N],f[2][1<<N][N],num[1<<N],cnt[1<<N],t[1<<N][2],tot;
inline int Mod(int x) {return x<mod?x:x-mod;}
inline void Add(int&x,int y) {x=Mod(x+y);}
inline int Ksm(int a,int n,int ans=1) {for(; n; n>>=1,a=1ll*a*a%mod)if(n&1)ans=1ll*ans*a%mod;return ans;}
int C(ll a,int b,int ans=1) {for(int i=1; i<=b; ++i)ans=1ll*ans*((a-i+1)%mod)%mod*Ksm(i,mod-2)%mod;return ans;}
inline int Solve1(int ans=0) {
	for(int i=0; i<(1<<m); ++i) {
		int opt=1;ll S=0;
		for(int j=0; j<m; ++j)if(i>>j&1)opt=-opt,S+=a[j]+1;
		if(S<=n)ans=Mod(Mod(ans+opt*C(n-S+m-1,m-1))+mod);
	} return ans;
}
inline int Solve2(int ans=0) {
	if(n&1)return 0;
    int nw=0;f[nw][S=(1<<m)-1][0]=1;
    for(int i=59; ~i; --i) {
    	nw^=1;for(int j=0; j<=S; ++j)for(int k=0; k<m; ++k)f[nw][j][k]=0;
		for(int j=0,tmp; j<=S; ++j)
			for(int k=0; k<m; ++k)if(tmp=f[nw^1][j][k]) {
    			int ct=0;for(int l=0; l<m; ++l)ct+=!(j>>l&1);
				for(int l=j,bj,num; 1; l=(l-1)&j) {
					bj=1;for(int r=0; r<m; ++r)if((j>>r&1)&&!(l>>r&1)&&!(a[r]>>i&1))bj=false;
					if(bj) {
						for(int r=num=0; r<m; ++r)if((j>>r&1)&&(l>>r&1)&&(a[r]>>i&1))++num;
						for(int r=num&1,A; r<=ct; r+=2)
							if((r+num>>1)<=k&&(A=(k-((r+num)>>1)<<1)+(n>>i&1))<m)Add(f[nw][l][A],1ll*tmp*c[ct][r]%mod);
					} if(!l)break;
				}
			}
	}
	for(int j=0; j<=S; ++j)ans=Mod(ans+f[nw][j][0]);return ans;
}
int main() {
	cin>>n>>m;
	for(int i=0; i<m; ++i)cin>>a[i];
	for(int i=0; i<=m; ++i)c[i][0]=1;
	for(int i=1; i<=m; ++i)for(int j=1; j<=i; ++j)c[i][j]=Mod(c[i-1][j]+c[i-1][j-1]);
	cout<<Mod(Solve1()-Solve2()+mod);
	return 0;
}