HDU 多校 2023 Round6 1007 Competition
command_block
·
·
个人记录
题意：你有两个变量 V,W，初始时 V=0,W=1。
接下来有 n+m 场比赛，其中你赢了 n 场输了 m 场。
你赢一场比赛，则 V 变为 V+2，然后 W 变为 W\times V。你输一场比赛，则 V 变为 V-1。
对于所有可能的输赢情况，求出 W 最终取值的和。
------------
一车人套数据过了这题（悲）
首先考虑 DP，设 $f[n][k]$ 为 $n$ 场比赛输了 $k$ 场的答案，则目前的 $V=-k+2(n-k)=2n-3k$。有转移
$$
f[n][k]=[k\geq 1]f[n-1][k-1]+(2n-3k)f[n-1][k]
$$
构造生成函数。记 $F_n(x)=\sum_{i=0}^{n}F[n][k]x^k$，则有转移
$$
F_n(x)=xF_{n-1}(x)-3xF'_{n-1}(x)+2nF_{n-1}(x)
$$
有三项，不好做。考虑将 $xF_{n-1}(x)-3xF'_{n-1}(x)$ 合成一项。等式左右两侧同时乘 $e^{-x/3}$ 得
$$
F_n(x)e^{-x/3}=xF_{n-1}(x)e^{-x/3}-3xF'_{n-1}(x)e^{-x/3}+2nF_{n-1}(x)e^{-x/3}
$$
由 $(F_n(x)e^{-x/3})'=F_n'(x)e^{-x/3}-F_n(x)e^{-x/3}/3$，可以合二为一。
$$
F_n(x)e^{-x/3}=-3x(F_{n-1}(x)e^{-x/3})'+2nF_{n-1}(x)e^{-x/3}
$$
记 $H_n(x)=F_n(x)e^{-x/3}$。
$$
H_n(x)=-3xH_{n-1}(x)'+2nH_{n-1}(x)
$$
提取系数可得
$$
H_n[k]=(2n-3k)H_{n-1}[k]
$$
$$
H_n[k]=\prod_{i=1}^n(2i-3k)H_0[k]
$$
其中 $F_0(x)=1,H_0(x)=e^{-x/3}$。
$H_n[k]$ 类似下降幂容易 $O(n)$ 递推，然后只需要卷 $e^{x/3}$ 恢复到 $F_n$。
答案只要一项，$O(n)$ 卷积即可。应该是爆标了。