BZOJ4589 Hard Nim

题目链接

题意

有 $n$ 堆石子,每堆石子个数是小于等于 $m$ 的质数,现在对这些石子玩 Nim 游戏,问后手必胜的方案数
$1\leq n \leq 10^9 , 2\leq m \leq 50000 $

题解

一道 $FWT$ 模板题
设 $F_n$ 表示考虑前 $n$ 堆石子,每堆石子数目异或值对应的生成函数,则
$$ F_n(i)=\sum_{j\oplus k = i} F_{n-1}(j) \cdot F_1(k) $$

然后发现可以 $FWT$ 完后做快速幂,于是问题就解决了
需要注意的是,如果自己打快读记得判断 EOF

代码

#define MAX_N 1000007
#define MX 200000
#define MOD 1000000007
#define INV2 500000004
typedef long long ll;

template <typename _T> inline bool read (_T& x) {
    x = 0;
    reg _T y = 1;
    reg char c = getchar();
    while ((c < '0' || '9' < c) && c != EOF) {
        if (c == '-') y = -1;
        c = getchar();
    }
    if (c == EOF) return false;
    while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getchar();
    x *= y;
    return true;
}

int N, P;
int pri[MAX_N], tot;
int f[MAX_N], g[MAX_N];
bool ntPri[MAX_N];

inline void init () {
    for (int i = 2; i <= MX; ++i) {
        if (!ntPri[i])
            pri[++tot] = i;
        for (int j = 1; j <= tot; ++j) {
            if (i * pri[j] > MX) break;
            ntPri[i * pri[j]] = true;
            if (i % pri[j] == 0)
                break;
        }
    }
}

inline void FWT (int *A, int M, int type) { //xor
    for (int i = 1; i < M; i <<= 1) {
        for (int j = 0, L = i << 1; j < M; j += L) {
            for (int k = j, x, y; k < j + i; ++k) {
                x = A[k], y = A[k + i];
                A[k] = 1LL * (1LL * x + 1LL * y) % MOD, A[k + i] = 1LL * (1LL * x - 1LL * y + MOD) % MOD;
                if (type == -1)
                    A[k] = 1LL * A[k] * INV2 % MOD, A[k + i] = 1LL * A[k + i] * INV2 % MOD;
            }
        }
    }
}

int main () {
    init();
    while (read(N) && read(P)) {
        memset(f, 0, sizeof(f));
        memset(g, 0, sizeof(g));
        for (int i = 1; i <= tot && pri[i] <= P; ++i)
            f[pri[i]] = 1;
        int M = 1;
        while (M <= P) M <<= 1;
        FWT(f, M, 1);
        for (int i = 0; i < M; ++i)
            g[i] = 1;
        while (N) {
            if (N & 1) {
                for (int i = 0; i < M; ++i)
                    g[i] = 1LL * g[i] * f[i] % MOD;
            }
            N >>= 1;
            for (int i = 0; i < M; ++i)
                f[i] = 1LL * f[i] * f[i] % MOD;
        }
        FWT(g, M, -1);
        printf("%d\n", g[0] % MOD);
    }
    return 0;
}

sys_con

OIer,常规 / 竞赛都渣得不行