「BZOJ 4589」Hard Nim

NOIP 之后就写了这么个 simple 题

BZOJ 4589

题意

你有 $n$ 堆有序的石子，每堆的数量都是 $\le m$ 的一个质数

你要玩 Nim游戏，问有多少种方案先手必败

$n\le 10^9, m\le 5*10^4$

---

做法

相当于有序选出 $n$ 个可以重复的质数使异或和为 $0$ 的方案数

定义卷积是异或卷积，直接 FWT 快速幂就好了

单次 $\mathcal O(m\log n)$

---

代码

#include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>

using namespace std;
#define ll long long

const int N = 50005, M = 1<<16, P = 1000000007;
int cnt, n, m, l, prime[N], f[M], g[M];
bool p[N];
inline int Pow(ll x, int y=P-2){
	int ans=1;
	for(; y; y>>=1, x=x*x%P) if(y&1) ans=ans*x%P;
	return ans;
}
inline void FWT(int *f, int g){
	for(int i=1; i<l; i<<=1) for(int j=0; j<l; j+=i<<1)
		for(int k=j; k<j+i; ++k){
			int x=f[k], y=f[k+i];
			f[k]=(x+y)%P, f[k+i]=(P+x-y)%P;
		}
	if(g==-1) for(int i=0, I=Pow(l); i<l; ++i) f[i]=(ll)f[i]*I%P;
}
inline void mul(int *f, int *g){ for(int i=0; i<l; ++i) f[i]=(ll)f[i]*g[i]%P;}
int main() {
	for(int i=2; i<=50000; ++i){
		if(!p[i]) prime[++cnt]=i;
		for(int j=1; j<=cnt && i*prime[j]<=50000; ++j){
			p[i*prime[j]]=1;
			if(i%prime[j]==0) break;
		}
	}
	while(~scanf("%d%d", &n, &m)){
		memset(f, 0, sizeof f);
		for(int i=1; i<=cnt && prime[i]<=m; ++i) f[prime[i]]=1;
		for(l=1; l<=m; l<<=1);
		FWT(f, 1);
		memcpy(g, f, l<<2);
		for(--n; n; n>>=1, mul(f, f)) if(n&1) mul(g, f);
		FWT(g, -1);
		printf("%d\n", g[0]);
	}
	return 0;
}