CF1842G Tenzing and Random Operations 题解
方法一：组合意义
虽然确实是对的但是怎么想出来。
方法二：大力推式子
设 \(f_{i,j}\) 表示考虑前 \(i\) 个位置，执行了 \(j\) 次操作的方案权值和，则有：
\[f_{i,k}=(a+vk)\sum_{j=0}^k{k\choose j}f_{i,j}
\]
进一步得到
\[\frac {f_{i,k}}{k!}=(a+vk)\sum_{j=0}^k\frac{f_{i,j}}{j!}\frac1{(k-j)!}
\]
于是设 \(F_i(x)=\sum_{j}\frac{f_{i,j}}{j!}x^j\)，转移化为：
\[\begin{aligned}
F_i(x)&=\sum_k\frac {f_{i,k}}{k!}x^k\\
&=\sum_k(a+vk)\sum_{j=0}^k\frac{f_{i,j}}{j!}\frac1{(k-j)!}x^k\\
&=a\sum_k\sum_{j=0}^k\frac{f_{i,j}}{j!}\frac1{(k-j)!}x^k+v\sum_kk\sum_{j=0}^k\frac{f_{i,j}}{j!}\frac1{(k-j)!}x^k\\
&=aF_{i-1}(x)e^x+v\sum_k\sum_{j=0}^k{j\choose k}f_{i,j}\frac{x^k}{(k-1)!}\\
&=aF_{i-1}(x)e^x+vx\sum_k\left[\sum_{j=0}^k{j\choose k}f_{i,j}\right]\frac{x^{k-1}}{(k-1)!}\\
&=aF_{i-1}(x)e^x+vx(F_{i-1}(x)e^x)'\\
&=aF_{i-1}(x)e^x+vxF_{i-1}(x)e^x+vxF_{i-1}'(x)e^x\\
&=e^x(aF_{i-1}(x)+vxF_{i-1}(x)+vxF_{i-1}'(x))
\end{aligned}
\]
递推的每一项都乘上一个定值 \(val_i\)，那么我们完全可以设 \(dp_i=(\prod_jval_j)f_i\)，即拨出一个 \(\prod_jval_j\)，然后数学归纳法证明。类似技巧还用在"P10219 [省选联考 2024] 虫洞"。
设 \(F_i(x)=G_i(x)e^{ix}\)，则：
\[\begin{aligned}
G_i(x)e^{ix}&=aG_{i-1}(x)e^{ix}+vx(G_{i-1}(x)e^{ix})'\\
&=aG_{i-1}(x)e^{ix}+vxiG_{i-1}(x)e^{ix}+vxG_{i-1}'(x)e^{ix}\\
G_i(x)&=aG_{i-1}(x)+vxiG_{i-1}(x)+vxG_{i-1}'(x)
\end{aligned}
\]
所以 \(g_{i,j}=ag_{i-1,j}+vig_{i-1,j-1}+vjg_{i-1,j}=(a+vj)g_{i-1,j}+vig_{i-1,j-1}\)，这直接 \(O(n^2)\) 求解。
所以
\[\begin{aligned}
ans&=\frac{[\frac{x^m}{m!}]F_n(x)}{n^m}\\&=\frac{m!}{n^m}\sum_{i}\frac{n^i}{i!}g_{n,m-i}\\&=\sum_{i}n^{i-1}g_{n,i}i!{m\choose i}
\end{aligned}
\]