【题解】BZOJ 4589 Hard Nim

请注意,本文编写于 97 天前,最后修改于 97 天前,其中某些信息可能已经过时。

Problem

有 $n$ 堆石子,每堆石子的数目为不超过 $m$ 的质数,求后手必胜的局面数

Thought

后手必胜,当且仅当所有石子的异或和为 $0$

问题转化为有多少种情况所有石子的异或和为 $0$

直接 $FWT$ 快速幂就好了?

和 $FFT$ 不同它的卷积严格在 $2^n$ 之内,并不会导致溢出啥的,所以就省了很多操作

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 65536;
const int mod = 1000000007;
const int inv2 = 500000004;
int a[N], ans[N];
bool no[N];
int pri[N], priCnt;
int n, m;
void getPri() {
    for(int i = 2; i < N; ++ i) {
        if(!no[i])
            pri[++ priCnt] = i;
        for(int j = 1; j <= priCnt && i * pri[j] < N; ++ j) {
            no[i * pri[j]] = 1;
            if(i % pri[j] == 0) break;
        }
    }
}
void FWT_XOR(int *a, int n, int f) {
    for(int i = 1; i < n; i <<= 1)
        for(int j = 0; j < n; j += (i << 1))
            for(int k = 0; k < i; ++ k) {
                int x = a[j + k], y = a[i + j + k];
                a[j + k] = (x + y) % mod;
                a[i + j + k] = (x - y + mod) % mod;
                if(f == - 1) {
                    a[j + k] = 1ll * a[j + k] * inv2 % mod;
                    a[i + j + k] = 1ll * a[i + j + k] * inv2 % mod;
                }
            }
}
int qpow(int b) {
    memset(ans, 0, sizeof(ans));
    ans[0] = 1;
    FWT_XOR(ans, N, 1);
    FWT_XOR(a, N, 1);
    while(b) {
        if(b & 1)
            for(int i = 0; i < N; ++ i)
                ans[i] = 1ll * ans[i] * a[i] % mod;
        for(int i = 0; i < N; ++ i)
            a[i] = 1ll * a[i] * a[i] % mod;
        b >>= 1;
    }
    FWT_XOR(ans, N, - 1);
    return ans[0];
}
int main() {
    getPri();
    while(~scanf("%d %d", &n, &m)) {
        memset(a, 0, sizeof(a));
        for(int i = 1; i <= priCnt && pri[i] <= m; ++ i)
            a[pri[i]] = 1;
        printf("%d\n", qpow(n));
    }
    return 0;
}
Comments

添加新评论