[笔记] RNG and XOR

最初 $x=0$，每一次操作以 $p_i$ 概率选择 $i$ 并将 $x$ 设为 $x\otimes i$（异或），问对于所有 $k$ （$1\le k\le 2^n$）期望操作多少次能第一次变成 $k$。

$1\le n\le 18$

题目链接

---

思路

一眼出式子：
$$
f_i=1+\sum_v p_v\cdot f_{v\otimes i}
$$
其中 $f_0=0$。然后只会 $O\left(\left(2^n\right)^3\right)$ 高斯消元了，显然过不了。

注意到异或，我们来考虑 FWT。有下面的式子：

$$ \left[f_0,f_1,f_2,\cdots\right]\otimes\left[p_0,p_1,p_2,\cdots\right]\\ =[?,f_1-1,f_2-1,f_3-1,\cdots] $$

这里的乘法是 FWT 异或卷积。$?$ 的取值是未定义的，因为我们规定了 $f_0$ 等于 0，但是实际乘法乘出来的东西不一定是这个。

考虑一下发现 $?$ 应该是 $(f_0+2^n-1)$，因为卷积之后新序列的和是等于原来两个序列的和的积的，又因为 $\sum_i p_i=1$，所以可以推出来。

现在一个等式两个未知还是没法搞，考虑弄掉右边。我们发现

$$ \begin{aligned} c_k&=\sum_{i\otimes j=k}a_i\cdot b_j\\ &=a_k\cdot b_0+\sum_{i\otimes j=k,j\ne0}a_i\cdot _j \end{aligned} $$

我们把 $b_0$ 减个 1 可以对于每个 $i$ 把 $c_i$ 削掉 $a_i$，然后就有：

$$ \left[f_0,f_1,f_2,\cdots\right]\otimes\left[p_0-1,p_1,p_2,\cdots\right]\\ =[2^n-1,-1,-1,\cdots] $$

然后就是 $A\otimes B=C$，$A=C\otimes B^{-1}$ 的形式了，FWT 求逆带走。FWT 的指数是模意义下的，所以本身就是循环卷积，FWT 后求逆元然后再 FWT 回去就是 FWT 求逆。

有个小问题。因为 FWT 后第 0 项是序列所有元素之和，因此中间那个 FWT 后第 0 项是 0，右边那个也是，导致我们没法反推出左边的 FWT 第 0 项到底是什么。实际做的时候，我们是直接 $a_i=c_i\cdot b_i^{-1}$ 次方，算的是 $a_0=0$ 了，但实际上并不对。我们注意到，$f_0$ 对左边的 FWT 每一项都贡献了一个 $f_0$，所以我们改变了 $f_0$ 的值对其它项的影响是线性且系数为 1 的，所以我们每一项都减一个 $f_0$ 就好了。

也就是说，在下面的代码里面加一个 w[0] = rand() % mod; 对计算过程没有任何影响。

代码

// Mivik 2020.12.25
#include <mivik.h>

#include <tuple>

MI cin;

typedef long long qe;

const int $n = 18;
const int $s = 1 << $n;
const int mod = 998244353;

int n, L, W;
int v[$s], w[$s];
inline int pro(int x) { return x >= mod? x - mod: x; }
inline int per(int x) { return x < 0? x + mod: x; }
inline qe ksm(qe x, int p = mod - 2) {
	qe ret = 1;
	for (; p; p >>= 1, (x *= x) %= mod) if (p & 1) (ret *= x) %= mod;
	return ret;
}
inline int div2(int x) { return ((x & 1)? x + mod: x) >> 1; }
template<bool rev>
inline void fwt(int *v) {
	for (int i = 1, q = 2; i < L; q = (i = q) << 1)
	for (int j = 0; j < L; j += q)
	for (int k = 0; k < i; ++k) {
		int &x = v[j | k], &y = v[i | j | k];
		std::tie(x, y) = std::make_tuple(
			pro(x + y),
			per(x - y)
		);
	}
	if (!rev) return;
	for (int i = 0; i < L; ++i)
		v[i] = (qe)v[i] * W % mod;
}
int main() {
	cin > n; W = ksm(L = 1 << n);
	int sum = 0;
	for (int i = 0; i < L; ++i)
		sum = pro(sum + (v[i] = R));
	sum = ksm(sum);
	for (int i = 0; i < L; ++i) {
		v[i] = (qe)v[i] * sum % mod;
		w[i] = mod - 1;
	}
	w[0] = L - 1;
	v[0] = per(v[0] - 1);
	fwt<0>(w); fwt<0>(v);
	for (int i = 0; i < L; ++i)
		w[i] = (qe)w[i] * ksm(v[i]) % mod;
	// w[0] = rand() % mod;
	fwt<1>(w);
	for (int i = 0; i < L; ++i)
		cout < per(w[i] - w[0]) < endl;
}