「bzoj4589」Hard Nim - 博弈论+SG函数+FWT | Bill Yang's Blog

「bzoj4589」Hard Nim - 博弈论+SG函数+FWT

题目大意

    Claris和NanoApe在玩石子游戏,他们有$n$堆石子,规则如下:

  1. Claris和NanoApe两个人轮流拿石子,Claris先拿。
  2. 每次只能从一堆中取若干个,可将一堆全取走,但不可不取,拿到最后$1$颗石子的人获胜。
        不同的初始局面,决定了最终的获胜者,有些局面下先拿的Claris会赢,其余的局面Claris会负。
        Claris很好奇,如果这$n$堆石子满足每堆石子的初始数量是不超过m的质数,而且他们都会按照最优策略玩游戏,那么NanoApe能获胜的局面有多少种。
        由于答案可能很大,你只需要给出答案对$10^9+7$取模的值。

题目分析

将素数筛出来,根据SG定理,可以知道相当于求异或等于$0$的方案数。
构造出生成函数,做一次异或卷积即可,使用FWT加速。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>

using namespace std;

typedef long long LL;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {
if(x=='-')bj=-1;
x=getchar();
}
while(isdigit(x)) {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=1<<16,maxm=50005;
const int mod=1e9+7,inv2=5e8+4;

struct FastWalshTransform {
int n;
void init(int n) {
this->n=n;
}
void transform(LL *a,LL mul) {
for(int len=2; len<=n; len<<=1) {
int mid=len>>1;
for(LL *p=a; p!=a+n; p+=len)
for(int i=0; i<mid; i++) {
LL x=p[i],y=p[mid+i];
p[i]=(x+y)*mul%mod;
p[mid+i]=(x-y+mod)*mul%mod;
}
}
}
void fwt(LL *a) {
transform(a,1);
}
void ufwt(LL *a) {
transform(a,inv2);
}
} wtf;

LL a[maxn],b[maxn];
int n,m,Prime[maxn],cnt=0;
bool vst[maxm];

void Prime_Table(int n) {
for(int i=2; i<=n; i++) {
if(!vst[i])Prime[++cnt]=i;
for(int j=1; j<=cnt&&i*Prime[j]<=n; j++) {
vst[i*Prime[j]]=1;
if(i%Prime[j]==0)break;
}
}
}

int main() {
Prime_Table(50000);
while(~scanf("%d%d",&n,&m)) {
int t=1;
while(t<=m)t<<=1;
wtf.init(t);
fill(a,a+t,0),fill(b,b+t,0);
for(int i=1; i<=cnt&&Prime[i]<=m; i++)a[Prime[i]]=1;
b[0]=1;
wtf.fwt(a),wtf.fwt(b);
for(; n; n>>=1) {
if(n&1)for(int i=0; i<t; i++)b[i]=a[i]*b[i]%mod;
for(int i=0; i<t; i++)a[i]=a[i]*a[i]%mod;
}
wtf.ufwt(b);
printf("%lld\n",b[0]);
}
return 0;
}
姥爷们赏瓶冰阔落吧~
0%