BZOJ4589 Hard Nim < FWT >

Problem

Hard Nim

Description

和在玩石子游戏，他们有堆石子，规则如下：

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

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

Input

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

Output

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

Sample Input

1
2

3 7
4 13

Sample Output

1
2

6
120

HINT

每组数据有, 。
不超过组数据。

Source

Topcoder SRM 518 Div1 Hard Nim By Tangjz

标签：FWT

Solution

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

预处理不超过的质数，设有个。设为一个数组，其中，则均为。用推，可知。同理。这样做次即可得到。最终答案为。
注意到从推到是异或卷积的形式，于是可以用优化，总复杂度。

Code

#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;
}