Description

题库链接

两人玩 \(nim\) 游戏，\(n\) 堆石子，每堆石子初始数量是不超过 \(m\) 的质数，那么后手必胜的方案有多少种。对 \(10^9+7\) 取模。

\(1\leq n\leq 10^9,2\leq m\leq 50000\)

Solution

我们记多项式 \(A(x)\) ，对于 \(x_i\) 若 \(i\leq m\) 且 \(i\) 为质数，那么 \(x_i\) 的系数为 \(1\) ，其余情况系数为 \(0\) 。

显然当 \(n=2\) 时，令多项式

\[C(x)=A(x)\oplus A(x)\]

其中 \(\oplus\) 为按位异或。那么 \(c_0\) 即为答案。

更多地， \(C(x)=A^n(x)\) ，那么 \(c_0\) 就是 \(n\) 堆石子的方案数。

\(FWT\) 乱搞一下即可。

Code

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9+7, N = 50000;

int isprime[N+5], prime[N+5], tot, n, m, len, inv2;

int f[N*2+5], a[N*2+5];

int quick_pow(int a, int b) {

    int ans = 1;

    while (b) {

    if (b&1) ans = 1ll*ans*a%mod;

    b >>= 1, a = 1ll*a*a%mod;

    }

    return ans;

}

void get_prime() {

    memset(isprime, 1, sizeof(isprime)); isprime[1] = 0;

    for (int i = 2; i <= N; i++) {

    if (isprime[i]) prime[++tot] = i;

    for (int j = 1; j <= tot && i*prime[j] <= N; j++) {

        isprime[i*prime[j]] = 0;

        if (i%prime[j] == 0) break;

    }

    }

}

void FWT(int *A, int o) {

    for (int i = 1; i < len; i <<= 1)

    for (int j = 0; j < len; j += (i<<1))

        for (int k = 0; k < i; k++) {

        int x = A[k+j], y = A[k+j+i];

        A[k+j] = (x+y)%mod, A[k+j+i] = (x-y+mod)%mod;

        if (o == -1) A[k+j] = 1ll*A[k+j]*inv2%mod, A[k+j+i] = 1ll*A[k+j+i]*inv2%mod;

        }

}

void work() {

    inv2 = quick_pow(2, mod-2);

    get_prime();

    while (~scanf("%d%d", &n, &m)) {

    memset(f, 0, sizeof(f));

    for (int i = 1; i <= tot && prime[i] <= m; i++) f[prime[i]] = 1;

    memset(a, 0, sizeof(a)); a[0] = 1;

    for (len = 1; len <= m; len <<= 1);

    FWT(a, 1), FWT(f, 1);

    while (n) {

        if (n&1) for (int i = 0; i < len; i++) a[i] = 1ll*a[i]*f[i]%mod;

        for (int i = 0; i < len; i++) f[i] = 1ll*f[i]*f[i]%mod;

        n >>= 1;

    }

    FWT(a, -1); printf("%d\n", a[0]);

    }

}

int main() {work(); return 0; }