题解：AT_agc034_f [AGC034F] RNG and XOR

· · 题解

[AGC034F] RNG and XOR

考虑 dp 转移。

设 p_i=\frac{A_i}{\sum A} 表示异或 i 的概率。

定义 f_i 表示走到 i 的期望步数，有初始状态 f_0=0。

转移：

f_i=1+\sum_{j=0}^{2^n-1}f_{i \operatorname{xor} j}\times p_{j}

发现形如异或卷积。

即为：(f_0,f_1,\dots,f_{2^n-1})\times (p_0,p_1,\dots,p_{2^n-1})=(C,f_{1}-1,f_{2}-1,\dots,f_{2^n-1}-1)。

因为 f_0=0，不是 fwt 的形式，考虑解出 C。

考虑卷积前后的每一项系数之和。左侧式子写成：

\sum_{i=0}^{2^n-1}\sum_{j\operatorname{xor}k=i}f_jp_k

由于每一对 j,k 都能够被计算一次，所以可以改写为：

\sum_{j=0}^{2^n-1}\sum_{k=0}^{2^n-1}f_jp_k\\ =(\sum_{j=0}^{2^n-1}f_j)(\sum_{k=0}^{2^n-1}p_k)\\

由于 \sum p_k=1，所以左边的系数和为 \sum f_j。

右边的系数之和显然容易计算。所以有等式：

\sum_{j=0}^{2^n-1}f_j=C+\sum_{j=1}^{2^n-1}(f_j-1)\\ \sum_{j=0}^{2^n-1}f_j=C-(2^n-1)+\sum_{j=1}^{2^n-1}f_j\\ C=(2^n-1)+f_0\\

现在卷积的形式好看了。

即：(f_0,f_1,\dots,f_{2^n-1})\times (p_0,p_1,\dots,p_{2^n-1})=(f_0+2^n-1,f_{1}-1,f_{2}-1,\dots,f_{2^n-1}-1)。

右边的 f 不好计算，考虑卷积过程中减去。

发现把 p_0\leftarrow p_0-1，右边每一项都将减去 f_i。

即：(f_0,f_1,\dots,f_{2^n-1})\times (p_0-1,p_1-1,\dots,p_{2^n-1}-1)=(2^n-1,-1,-1,\dots,-1)。

显然：

(f_0,f_1,\dots,f_{2^n-1})=\frac{(2^n-1,-1,-1,\dots,-1)}{(p_0-1,p_1-1,\dots,p_{2^n-1}-1)}

但是还有一个问题：对于 f_0，最后求出来不一定的是 0。

怎么办？观察转移式，发现若 f_0 增加 \Delta，那么对于任意 i，f_i 都只能增加 \Delta 才能合法。

所以答案直接输出 f_i-f_0 即可。