Solution - Atcoder AGC034F RNG and XOR

考虑到这个边权是 \(\oplus\)，那么说明对于 \((u, v)\)，\(u\to v\) 和 \(v\to u\) 的边权实质是相同的。
那么对于 \(0\to x\)，就可以反过来，记录下对应的路径，从 \(x\) 开始走，那么第一次走到 \(0\) 的时候也就是从 \(0\) 第一次走到 \(x\) 的时候。
于是就转化为了 \(x\) 为起点，第一次到达 \(0\) 的期望时间。

记 \(a_i\) 为概率，\(E(i)\) 为以 \(i\) 点为起点的期望。
那么就有 \(E(i) = \begin{cases} 0 & i = 0\\ \sum\limits_{j = 0}^{2^n - 1} a_j E(i\oplus j) + 1 & i\not = 0\end{cases}\)。
考虑到这是个 \(\oplus\) 的形式，于是可以考虑写成异或卷积的形式。
就有 \((E(0), E(1), \cdots)\times (a_0, a_1, \cdots) + (1, 1, \cdots) = (c, E(1), \cdots)\)，这里的 \(\times\) 指异或卷积。
同时这里引入了一个 \(c\)，这是因为实际上 \(E(0) = 0\)，但是左边这一部分算出来的 \(E(0)\) 不为 \(0\)，就用 \(c\) 来补足。
考虑这个 \(c\) 应该是多少，因为 \(\sum\limits_{i = 0}^{2^n - 1} a_i = 1\)，所以 \((E(0), E(1), \cdots)\times (a_0, a_1, \cdots)\) 后系数和不会发生变化，那么就有 \(c = \sum\limits_{i = 0}^{2^n - 1} 1 = 2^n - 1\)。

于是有 \((E(0), E(1), \cdots)\times (a_0, a_1, \cdots) + (1, 1, \cdots) = (2^n, E(1), \cdots)\)。
考虑把 \((1, 1, \cdots)\) 移到右边，有 \((E(0), E(1), \cdots)\times (a_0, a_1, \cdots) = (2^n - 1, E(1) - 1, \cdots)\)。
发现右边项的 \(E(i)\) 系数都为 \(1\)，于是可以考虑在 \(a_0\) 处 \(-1\)。
就有 \((E(0), E(1), \cdots)\times (a_0 - 1, a_1, \cdots) = (2^n - 1, -1, \cdots)\)。

然后就可以解 \(E\) 了。
但是能发现这样解出来的 \(E\) 是不唯一的。
进一步发现，可能的 \(E\) 在每一项都 \(+ k\) 也可以。
但是因为有 \(E(0) = 0\)，所以 \(E(i) - E(0)\) 就是 \(i\) 的答案。

时间复杂度 \(\mathcal{O}(2^n(n + \log \text{mod}))\)。

#include<bits/stdc++.h>
using ll = long long;
constexpr ll mod = 998244353, inv2 = mod + 1 >> 1;
inline ll qpow(ll a, ll b, ll v = 1) {
   while (b) b & 1 && ((v *= a) %= mod), (a *= a) %= mod, b >>= 1;
   return v;
}
const int maxn = 1 << 18;
int n;
inline void FWT(ll *f, ll val) {
   for (int i = 1; i <= n; i++)
      for (int j = 0; j < (1 << n); j += 1 << i)
         for (int k = 0, p = 1 << i - 1; k < p; k++) {
            ll x = f[j + k] * val % mod, y = f[j + k + p] * val % mod;
            f[j + k] = (x + y) % mod, f[j + k + p] = (mod + x - y) % mod;
         }
}
ll a[maxn], f[maxn], g[maxn];
int main() {
   scanf("%d", &n);
   ll sum = 0;
   for (int i = 0; i < (1 << n); i++) scanf("%lld", &a[i]), (sum += a[i]) %= mod;
   sum = qpow(sum, mod - 2);
   for (int i = 0; i < (1 << n); i++) (a[i] *= sum) %= mod;
   for (int i = 0; i < (1 << n); i++) f[i] = (mod - 1 + (i ? 0 : (1 << n))) % mod;
   for (int i = 0; i < (1 << n); i++) g[i] = (mod + a[i] - (i ? 0 : 1)) % mod;
   FWT(f, 1), FWT(g, 1);
   for (int i = 0; i < (1 << n); i++) (f[i] *= qpow(g[i], mod - 2)) %= mod;
   FWT(f, inv2);
   for (int i = 0; i < (1 << n); i++) printf("%lld\n", (mod + f[i] - f[0]) % mod);
   return 0;
}