这也太难了！这也太难了！这也太难了！
D AtCoder-AGC034F RNG and XOR
这类无穷游走的期望可以写出转移式子：
\[\begin{cases} E_i=0&i=0\\ E_i=1+\sum_{j\oplus k=i} E_j\times P_k&i>0 \end{cases} \]\(i>0\) 的情况按 FWT 异或卷积理解就是 \(E=E*P+I\)，但是放在 \(E_0=0\) 处不太合适，加上一个常数 \(c\)，变成 \(E+c=E*P+I\)。
考虑如何求得 \(c\)，似乎是比较套路的，左式系数之和就是 \(\sum E+c\)，右式中卷积的系数之和其实就是分配律，即 \(\sum E+c=\sum E\times \sum P+2^n\)，而 \(\sum P=1\)，因此 \(c=2^n\)。
于是写成 \(E*P-E=2^n-I\)，这里 \(E*P-E\)，也就是 \(E_i\) 在卷积中对 \(E_i\) 的贡献少了 \(1\)，对应就是 \(P_0\) 减少 \(1\)，即 \(E*(P-1)=2^n-I\)。
这个时候根据 FWT 已经可以写出 \(\mathrm{FWT}(E)=\dfrac{\mathrm{FWT}(2^n-I)}{\mathrm{FWT}(P-1)}\) 了，但是因为 \(\mathrm{FWT}(2^n-I)_0=0,\mathrm{FWT}(P-1)_0=\sum P-1=0\)，而 \(i>0\) 时 \(\mathrm{FWT}(P-1)_i<\sum P-1=0\)，因此只有 \(\mathrm{FWT}(E)_0\) 位置出错，且一定会出错。
假设 \(\mathrm{FWT(E)}_0\) 理应是 \(c'\)，那么 IFWT 回去时在每个位置都少加了 \(\dfrac{c'}{2^n}\)，且根据前面的 \(E_0=0\)，可以用这个确定的值去修正其他的值。
提交记录：Submission - AtCoder
E AtCoder-AGC038E Gachapon
肯定要 min-max 容斥。
关键是容斥完这个 \(E(\min)\) 也不好算，主要困难在不是每次选择都会有对当前集合的贡献产生，同时每个元素的要求次数 \(b_i\) 不同。
实际上我们可以求随机出一个在集合 \(T\) 里的元素的期望步数，根据几何分布可以得到这个期望为 \(\dfrac{\sum a}{\sum_{i\in T} a_i}\)，这样就排除了第一个难点，我们只需要考虑每次在 \(T\) 中随机的期望，最后再乘上 \(\dfrac{\sum a}{\sum_{i\in T} a_i}\) 就行。
这时候就类似在 \(|T|\) 维空间游走，每次在一维移动一次，停止条件是某一维达到了 \(b_i\)，这样期望次数就可以把每个状态 \((c_1,c_2,\cdots,c_{|T|})\) 的概率求和，加起来就是最终答案，而结尾状态有且仅有一个 \(c_i=b_i\) 并不好统计，不妨等价的把贡献统计在初始位置。
这样一个位置的概率实际就是多重集组合数乘当前排列每个数的概率：
\[\dbinom{\sum_{i\in T} c_i}{c_1,c_2,\cdots,c_{|T|}}\prod_{i\in T}\left(\dfrac{a_i}{\sum_{i\in T}a_i}\right)^{c_i}=\left(\sum_{i\in T} c_i\right)!\dfrac{1}{\left(\sum_{i\in T} a_i\right)^{\sum_{i\in T} c_i}} \prod_{i\in T}\dfrac{a_i^{c_i}}{c_i!} \]这样整个结果就是：
\[\sum_{T\subseteq S,T\neq \varnothing} (-1)^{|T|-1} \dfrac{\sum a\left(\sum_{i\in T} c_i\right)!}{\left(\sum_{i\in T}a_i\right)^{1+\sum_{i\in T} c_i}}\prod_{i\in T}\dfrac{a_i^{c_i}}{c_i!} \]发现答案之和 \(\sum a,\sum_{i\in T} a_i,\sum_{i\in T} c_i\) 有关，可以设计成状态来 DP，设 \(f_{i,j,k}\) 表示前 \(i\) 个数，当前 \(\sum_{i\in T} a_i=j,\sum_{i\in T} c_i=k\)，发现过程中需要知道每个 \(a_i,c_i\)，所以就是个背包的形式，容斥的系数 \(-1\)，每次取负就行，由于第一维和枚举 \(c_i\) 的总复杂度是 \(O(\sum b)\) 的，所以总复杂度是 \(O(n^3)\) 的。
提交记录：Submission - AtCoder
剩下的会了再写……
标签：right,乱写,dfrac,sum,多校,FWT,left,杂题,mathrm From： https://www.cnblogs.com/SoyTony/p/Multiple_School_Mathematics_Training_Problems_in_Xian_Ju