BZOJ4589 Hard Nim < FWT >

Posted on Symbols count in article: 811 Reading time ≈ 3 mins.

Problem

Hard Nim

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  128  MB\mathrm{Memory\;Limit:\;128\;MB}

Description

Claris\mathrm{Claris}和NanoApe\mathrm{NanoApe}在玩石子游戏，他们有nn堆石子，规则如下：

  1. Claris\mathrm{Claris}和NanoApe\mathrm{NanoApe}两个人轮流拿石子，Claris\mathrm{Claris}先拿。
  2. 每次只能从一堆中取若干个，可将一堆全取走，但不可不取，拿到最后1颗石子的人获胜。

不同的初始局面，决定了最终的获胜者，有些局面下先拿的Claris\mathrm{Claris}会赢，其余的局面Claris\mathrm{Claris}会负。
Claris\mathrm{Claris}很好奇，如果这nn堆石子满足每堆石子的初始数量是不超过mm的质数，而且他们都会按照最优策略玩游戏，那么NanoApe\mathrm{NanoApe}能获胜的局面有多少种。
由于答案可能很大，你只需要给出答案对109+710^9+7取模的值。

Input

输入文件包含多组数据，以EOF为结尾。
对于每组数据，输入一行两个正整数nn和mm。

Output

对于每组数据，输出一行一个整数表示答案。

Sample Input

1
2
3 7
4 13

Sample Output

1
2
6
120

HINT

每组数据有1≤n≤1091\le n\le10^9, 2≤m≤500002\le m\le50000。
不超过8080组数据。

Source

Topcoder SRM 518 Div1 Hard Nim By Tangjz

标签：FWT

Solution

FWT\mathrm{FWT}裸题。
由基础博弈可知，Nim\mathrm{Nim}游戏先手必胜的充要条件是所有石子堆个数异或和为00。于是答案为

∑a1⊕a2⊕⋯an=01\sum_{a_1\oplus a_2\oplus\cdots a_n=0}1

预处理不超过mm的质数，设有ll个。设xkx_k为一个数组，其中xk,y=∑a1⊕a2⊕⋯ak=y1x_{k,y}=\sum_{a_1\oplus a_2\oplus\cdots a_k=y}1，则x1,1∼x1,lx_{1,1}\sim x_{1,l}均为11。用x1x_1推x2x_2，可知x2,k=∑p⊗q=kx1,p⋅x1,qx_{2,k}=\sum_{p\otimes q=k}x_{1,p}\cdot x_{1,q}。同理xt,k=∑p⊕q=kx1,p⋅xt−1,qx_{t,k}=\sum_{p\oplus q=k}x_{1,p}\cdot x_{t-1,q}。这样做nn次即可得到xnx_n。最终答案为xn,0x_{n,0}。
注意到从xt−1x_{t-1}推到xtx_t是异或卷积的形式，于是可以用FWT\mathrm{FWT}优化，总复杂度O(T×nlog⁡n)O(T\times n\log{n})。

Code

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
#include <bits/stdc++.h>
#define MAX_N 65536
#define P 1000000007
#define inv2 500000004
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, l, cnt, pri[MAX_N+5];
lnt a[MAX_N+5]; bool NotPri[MAX_N+5];
void init() {
    NotPri[0] = NotPri[1] = true;
    for (int i = 2; i <= MAX_N; i++) {
        if (!NotPri[i]) pri[++cnt] = i;
        for (int j = 1; j <= cnt; j++) {
            if (i*pri[j] > MAX_N) break;
            NotPri[i*pri[j]] = true;
            if (i%pri[j] == 0) break;
        }
    }
}
lnt pow(lnt x) {
    lnt ret = 1;
    for (int k = n; k; k >>= 1, x = x*x%P)
        if (k&1) ret = ret*x%P;
    return ret;
}
void FWT(lnt *arr, int l) {
    for (int d = 1; d < l; d <<= 1)
        for (int i = 0; i < l; i += (d<<1))
            for (int j = i; j < i+d; j++) {
                lnt x = arr[j], y = arr[j+d];
                arr[j] = (x+y)%P, arr[j+d] = (x-y+P)%P;
            }
}
void UFWT(lnt *arr, int l) {
    for (int d = l>>1; d; d >>= 1)
        for (int i = 0; i < l; i += (d<<1))
            for (int j = i; j < i+d; j++) {
                lnt x = arr[j], y = arr[j+d];
                arr[j] = (x+y)%P*inv2%P;
                arr[j+d] = (x-y+P)%P*inv2%P;
            }
}
int main() {
    init();
    while (~scanf("%d%d", &n, &m)) {
        memset(a, 0, sizeof a); for (l = 1; l <= m; l <<= 1) ;
        for (int i = 1; i <= cnt && pri[i] <= m; i++) a[pri[i]] = 1;
        FWT(a, l); for (int i = 0; i < l; i++) a[i] = pow(a[i]);
        UFWT(a, l); printf("%lld\n", a[0]);
    }
    return 0;
}