034F
AGC034F 题解
FWT 入门题，很适合我这样的蒟蒻。 首先我们可以轻松的根据转移条件写出来一个优美的函数 \(T(i)=1+\sum_{j\oplus k=i}a_kT(j)\)，边界为 \(T(0)=0\)。 这个方程属于转移带环的 DP，处理方法一般是高斯消元，在这道题里会 T 飞。 但是我们又注意到后边是一个 ......
「题解」AGC034F RNG and XOR
$f_i$ 为变成 $i$ 的期望步数，那么 $f_0=0$，$f_i=1+\sum_{j=0}^{2^n-1}f_j\cdot p_{i\oplus j}$，理解为从 $i$ 走到 $0$ 的期望步数即可。 尝试用集合幂级数描述这个东西，如果不管 $f_0$ 那么就是 $F=F\times P+I ......
AGC034F RNG and XOR
类似随机游走，令 $f_i$ 为第一次操作到 $i$ 的期望操作次数，$p_i$ 为每次操作数为 $i$ 个概率，显然有： $$f_i=\begin{cases}0&i=0\\1+\sum\limits_{j\;\text{xor}\; k\ =\ i}p_jf_k &i\neq 0\end{cas ......
Solution AGC034F
$\mathtt{Description}$： 给定 $n$ 和一个长度为 $2^n$ 的数组 $A$ (从 $0$ 标号). 有一个初始为 $0$ 的变量 $x$ . 不断操作, 每次操作以 $\frac {A_i}{\sum_{j=0}^{2^n-1} A_j}$ 的概率将 $x$ 变成 $x\ ......