「Universal OJ」#310. 「UNR #2」黎明前的巧克力

主要思路

其实就是做 \((1 + 2x^{a_i})\) 的异或卷积得组成 \(0\) 的方案。一种想法是做多次 FWT，但是这样铁定超时。我们考虑观察一下性质。

其实考虑 FWT 的变换就是：

\[ b_i = \sum_{j} (-1)^{cnt(i \& j)} a_j \]

若干次 FWT 之后，每个位置要么是 \(3\)，要么是 \(1\)（位置 \(0\) 上的 \(1\) 对所有位置的贡献都是 \(1\)，\(a_i\) 位置上的 \(2\) 的贡献有可能是 \(2, -2\)）。那么其实最后的结果就是一 \(-1\) 的幂和 \(3\) 的幂的和。我们需要算出来这个指数然后搞个快速幂。

我们可以设置 \(-1\) 的指数为 \(x\)，那么 \(3\) 的指数就是 \(n – x\)。我们需要知道每个位置上的 \(x\)，可以考虑找一个方程。

有一个性质就是，FWT 的和就是和的 FWT。那我们可以做和然后 FWT，然后列方程 \(b_i = -1x + 3(n – x)\)，解出 \(x\) 后那么真正 FWT 之后的值为 \(c_i = (-1)^x + 3^{n – x}\)。

代码

// UOJ310.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e6 + 200, mod = 998244353, poly_siz = 1048576;

int n, ai[MAX_N], bi[MAX_N], ci[MAX_N], pw[MAX_N];

int fpow(int bas, int tim)
{
    int ret = 1;
    while (tim)
    {
        if (tim & 1)
            ret = 1LL * ret * bas % mod;
        bas = 1LL * bas * bas % mod;
        tim >>= 1;
    }
    return ret;
}

const int inv2 = fpow(2, mod - 2);

void fwt_xor(int *arr, int dft)
{
    for (int step = 1; step < poly_siz; step <<= 1)
        for (int j = 0; j < poly_siz; j += (step << 1))
            for (int k = j; k < j + step; k++)
            {
                int A = arr[k], B = arr[k + step];
                arr[k] = (0LL + A + B) % mod, arr[k + step] = (0LL + A + mod - B) % mod;
                if (dft == -1)
                    arr[k] = 1LL * arr[k] * inv2 % mod, arr[k + step] = 1LL * arr[k + step] * inv2 % mod;
            }
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]), bi[0]++, bi[ai[i]] += 2;
    for (int i = pw[0] = 1; i < poly_siz; i++)
        pw[i] = 3LL * pw[i - 1] % mod;
    fwt_xor(bi, 1);
    for (int i = 0; i < poly_siz; i++)
    {
        int x = (3LL * n + mod - bi[i]) % mod * inv2 % mod * inv2 % mod;
        ci[i] = (x & 1) ? (mod - pw[n - x]) % mod : (pw[n - x]);
    }
    fwt_xor(ci, -1), printf("%lld\n", (0LL + ci[0] + mod - 1) % mod);
    return 0;
}