AGC034F RNG and XOR

写出 DP 方程，有

$$
E _ i =
\begin {cases}
0, i = 0 \\
1 + \sum _ {j = 0} ^ {2 ^ n - 1} E _ j a _ {j \oplus i}
\end {cases}
$$

考虑写出集合幂级数的形式，有 $E = E _ 0 + \sum _ {i = 1} ^ {2 ^ n - 1} [x ^ i] (I + E * P)$ 。注意到因为对于 $i = 0$ 公式不适用，考虑单独算出 $[x ^ 0](I + E * P)$ 。将方程两侧全部相加，有 $\sum _ i E _ i = (2 ^ n + \sum _ i E _ i) - (1 + \sum _ {j = 0} ^ {2 ^ n - 1}E _ j a _ j)$ ，即 $[x ^ 0](I + E * P) = 2 ^ n$ 。那么有 $E = I + E * P - 2 ^ n$ 。即 $E = \frac {2 ^ n - I}{P - 1}$ 。

可以注意到一个问题，对于 $[x ^ 0]P$ ，因为有 $\sum _ {i = 0} ^ {2 ^ n - 1} (-1) ^ {|0 \wedge i|}p _ j = \sum _ i p _ i = 1$ ，那么求逆元的时候会出问题。事实上，对于 $E = I + E * P - 2 ^ n$ ，$[x ^ 0]$ 时恒成立。注意到 FWT 的展开式中，$i = 0$ 对所有 $i$ 都有 $[x ^ 0]$ 的贡献，不论 $[x ^ 0]$ 为多少，减去即可。

查看代码

#include <cstdio>
using namespace std;
template <class Type>
void read (Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        flag |= c == '-';
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    if (flag) x = ~x + 1;
}
template <class Type, class ...Rest>
void read (Type &x, Rest &...y) { read(x); read(y...); }
template <class Type>
void write (Type x)
{
    if (x < 0) putchar('-'), x = ~x + 1;
    if (x > 9) write(x / 10);
    putchar('0' + x % 10);
}
typedef long long LL;
const int N = 1 << 18, mod = 998244353, inv2 = 499122177;
int n, m, w[N], v[N];
int binpow (int b, int k = mod - 2)
{
    int res = 1;
    for (; k; k >>= 1, b = (LL)b * b % mod)
        if (k & 1) res = (LL)res * b % mod;
    return res;
}
void fwt (int *x, int op)
{
    for (int mid = 1; mid < m; mid <<= 1)
        for (int i = 0; i < m; i += mid << 1)
            for (int j = 0; j < mid; ++j)
            {
                int p = x[i | j], q = x[i | mid | j];
                x[i | j] = (LL)op * (p + q) % mod, x[i | mid | j] = (LL)op * (p - q) % mod;
            }
}
int main ()
{
    read(n); m = 1 << n;
    int sp = 0;
    for (int i = 0; i < m; ++i)
        read(w[i]), sp += w[i];
    sp = binpow(sp);
    for (int i = 0; i < m; ++i)
        w[i] = (LL)w[i] * sp % mod;
    --w[0], v[0] = m - 1;
    for (int i = 1; i < m; ++i) v[i] = -1;
    fwt(w, 1), fwt(v, 1);
    w[0] = 0;
    for (int i = 1; i < m; ++i)
        w[i] = (LL)binpow(w[i]) * v[i] % mod;
    fwt(w, inv2);
    int t = w[0];
    for (int i = 0; i < m; ++i)
        write((((LL)w[i] - t) % mod + mod) % mod), puts("");
    return 0;
}