【题解】「KrOI2021」Feux Follets —— Alpha1022

来支持一下 Qiuly /tyt

考虑先进行多点求值，问题转化为对给定的数列 $F_k$ 和 $1 \le m \le n$，计算
$$
\sum\limits_{|\pi|=m} F_{\mathrm{cyc}_{\pi}}
$$

我们自然考察计算
$$
\sum\limits_k F_k \sum\limits_{|\pi|=m} [\mathrm{cyc}_{\pi}=k]
$$

考虑
$$
\sum\limits_{1 \le |\pi| \le n} z^{|\pi|} t^{\mathrm{cyc}_{\pi}}
$$

根据 Symbolic Methods，显然其即
$$
G(z,t) = \mathrm e^{t(-\ln(1-z)-z)}
$$

考虑实际上我们需要计算
$$
\sum\limits_k F_k [t^k] G(z,t)
$$

首先考虑其转置
$$
\sum\limits_k F_k [z^k] G(z,t)
$$

注意 $G$ 满足微分方程
$$
\frac{\partial G(z,t)}{\partial z} = \frac{zt}{1-z} G(z,t)
$$

令 $G_k = [z^k]G(z,t)$，则其满足
$$
G_k = \frac1k\left[(k-1)G_{k-1}+tG_{k-2}\right]
$$

其转移容易用矩阵描述。那么对原问题的转置的计算方式无非就是考虑分治，同时维护区间内的矩阵连乘积和区间内的矩阵贡献和即可。
而对于原问题，我们应用转置原理将分治过程逐步改写即可。