一道有趣的题目

其实是今天考试题,话说昨天做了 FWT 题今天就考一道 FWT 题真巧

题意

给出 $n$ 堆石子,每堆石子个数为 $a_i$ ,然后删掉几堆石子(不能全删),问至少删多少堆使后手必胜

题解

设 $XOR$ 为所有 $a_i$ 的异或和,则题目可以转化为选最少的数是它们异或起来为 $XOR$

设 $f[i][j]$ 为选 $i$ 个数异或起来为 $j$ 的方案数(其实只要可能性就行),于是有
$$ f[i+j][x\oplus y]+=f[i][x]+f[j][y] $$
然后发现可以使用 FWT 加速,于是使用倍增预处理出 $f[2^i][j]$ 的值,至于如何选最少的数,也可以使用倍增,只需要找出选最多的数使它们异或起来不为 $XOR$ ,然后个数加一就是答案
由于我们只需要确定可行性,所以找个小数字模一下就行了

代码

#define MAX_N 1000007
#define MOD 10007
#define INV2 5004

int N, M, a[MAX_N], mx, XOR;
int f[MAX_N], g[22][MAX_N], h[MAX_N];

inline void input () {
    read(N);
    for (int i = 1; i <= N; ++i)
        read(a[i]), mx = std::max(mx, a[i]), XOR ^= a[i];
    int sum = 0;
    while (mx)
        sum++, mx >>= 1;
    M = (1 << sum);
}

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

inline void init () {
    for (int i = 1; i <= N; ++i)
        g[0][a[i]] = 1;
    g[0][0] = 1;
    FWT(g[0], M, 1);
    for (int i = 1; i <= 21; ++i) {
        for (int j = 0; j < M; ++j)
            g[i][j] = g[i - 1][j] * g[i - 1][j] % MOD;
    }
}

inline void solve () {
    memset(f, 0, sizeof(f));
    bool flag = false;
    int res = 0;
    for (int i = 21; i >= 0; --i) {
        memcpy(h, f, sizeof(h));
        if (flag) {
            FWT(f, M, 1);
            for (int j = 0; j < M; ++j)
                f[j] = g[i][j] * f[j] % MOD;
        } else {
            memcpy(f, g[i], sizeof(f));
        }
        FWT(f, M, -1);
        if (!f[XOR]) {
            flag = true;
            res += (1 << i);
        } else {
            memcpy(f, h, sizeof(f));
        }
    }
    printf("%d\n", N - res - 1);
}

int main () {
    freopen ("nim.in", "r", stdin);
    freopen ("nim.out", "w", stdout);
    input();
    init();
    if (XOR == 0) return printf("%d\n", N), 0;
    solve();
    return 0;
}

sys_con

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注