AGC034F 题解

FWT 入门题，很适合我这样的蒟蒻。

首先我们可以轻松的根据转移条件写出来一个优美的函数 \(T(i)=1+\sum_{j\oplus k=i}a_kT(j)\)，边界为 \(T(0)=0\)。

这个方程属于转移带环的 DP，处理方法一般是高斯消元，在这道题里会 T 飞。

但是我们又注意到后边是一个美丽的异或卷积，因此可以考虑用 FWT 优化转移。根据卷积我们推导 \(T=I+T\oplus A\)，其中函数 \(A\) 代表题目所给的序列。但是这样显然右边多了一个 \(2^n\)，所以 \(T+2^n=I+T\oplus A\)，然后根据广义乘法的运算法则，我们认为 \(T=\frac{I-2^n}{1-A}\)，因此可以直接上下分别 FWT 然后点值相除。

核心代码如下：

signed main()
{
    cin >> n;
    n = (1 << n);
    long long sum = 0;
    for (int i = 0; i < n; i++)
        cin >> a[i], sum += a[i];
    sum %= mod;
    sum = qpow(sum, mod - 2);
    for (int i = 0; i < n; i++)
        a[i] = 1ll * a[i] * sum % mod;
    a[0] = (a[0] - 1 + mod) % mod;
    b[0] = n - 1;
    for (int i = 1; i < n; i++)
        b[i] = mod - 1;
    fwt(a, 1), fwt(b, 1);
    for (int i = 0; i < n; i++)
        a[i] = 1ll * b[i] * qpow(a[i], mod - 2) % mod;
    fwt(a, -1);
    for (int i = 0; i < n; i++)
        printf("%d\n", (a[i] - a[0] + mod) % mod);
}