题解：CF2223F Zhily and Colorful Strings

· · 题解

据说我是场上唯一独立切了这个题的人类，写篇题解纪念一下吧。

经过一些观察就可以发现，最终的字符串一定是若干颜色段嵌套形成的树形结构。具体地，一种方案必然与一棵满足如下条件的有根森林形成双射：

很显然这里应该使用多元拉反去刻画（不会的可以去看 EI 哥哥 2021 年的集训队论文）。对于 m 元的多元幂级数组 \mathbf{F}=(F_1,F_2,\cdots,F_m)，F_i 表示以第 i 类点为根且规定根的颜色的满足上述条件的树的每种结点出现出现次数的多元幂级数（设形式元为 \mathbf{x}=(x_1,x_2,\cdots,x_m)），其树形复合方程为：

F_i=x_iG_i(F)=x_i(\dfrac{1}{1-\sum_{j=1}^m(c_j-[i=j])F_j})^{d_i-1}

记 T=1-\sum_{j=1}^mc_jx_j，即：

G_i=(\dfrac{1}{T+x_i})^{d_i-1}

有根森林的多元幂级数即为：

\dfrac{1}{1-\sum_{j=1}^mc_jF_j}

即 \dfrac{1}{T} 复合上 \mathbf{F}。

设 k_i=\dfrac{n_i}{d_i}，根据多元拉格朗日反演（记 \begin{Vmatrix}*\end{Vmatrix} 表示行列式）：

[\mathbf{x^k}]\dfrac{1}{T(\mathbf{F})}=[\mathbf{x^k}]\dfrac{1}{T}\mathbf{G^k}\begin{Vmatrix}[i=j]-\dfrac{x_j}{G_i(\mathbf{x})}\dfrac{\partial G_i(\mathbf{x})}{\partial x_j}\end{Vmatrix} =[\mathbf{x^k}]\dfrac{1}{T}\prod_{i=1}^m(\dfrac{1}{T+x_i})^{(d_i-1)k_i}\begin{Vmatrix}[i=j]-\dfrac{x_j}{(\dfrac{1}{T+x_i})^{d_i-1}}\dfrac{(d_i-1)(c_j-[i=j])}{(T+x_i)^{d_i}}\end{Vmatrix} =[\mathbf{x^k}]\dfrac{1}{T}\prod_{i=1}^m(\dfrac{1}{T+x_i})^{(d_i-1)k_i}\begin{Vmatrix}[i=j]-\dfrac{(d_i-1)(c_j-[i=j])x_j}{T+x_i}\end{Vmatrix}

考虑计算这个行列式：令 A=\begin{bmatrix}\dfrac{-(d_i-1)c_jx_j}{T+x_i}\end{bmatrix}，这个行列式即为 \det(A+\sum_{i=1}^n(1+\dfrac{(d_i-1)x_i}{T+x_i})e_{i,i})。A 中任取不少于两行与其对应的列，行列式都为 0，故这个行列式即为：

(\prod_{i=1}^m\dfrac{T+d_ix_i}{T+x_i})(1+\sum_{i=1}^m\dfrac{-(d_i-1)c_ix_i}{T+d_ix_i})

所求即为：

[\mathbf{x^k}]\dfrac{1}{T}\prod_{i=1}^m(\dfrac{1}{T+x_i})^{(d_i-1)k_i}(\prod_{i=1}^m\dfrac{T+d_ix_i}{T+x_i})(1+\sum_{i=1}^m\dfrac{-(d_i-1)c_ix_i}{T+d_ix_i})

根据泰勒展开，(\dfrac{1}{T+x_i})^t=e^{x_i\frac{\operatorname{d}}{\operatorname{d}T}}(\dfrac{1}{T})^t=\sum_{j=0}\dfrac{x_i^jT^{-t-j}(-t)^{\underline j}}{j!}，故最后的答案一定是 T^{-l}\sum_s*\prod_{i=1}^m(\dfrac{x_i}{T})^{s_i} 的形式，其中 l=1+\sum_{i=1}^m(d_i-1)k_i。而我们只关心 \sum_{i=1}^ms_i（其实还有 \prod_{i=1}^m\dfrac{c_i^{k_i-s_i}}{(k_i-s_i)!}，可以直接对于每个 i 乘进系数里面），并且 s_i\leq k_i，分治 NTT 对于每个 \sum_{i=1}^ms_i 计算 * 处系数即可。记 n=\sum_{i=1}^mk_i，时间复杂度 O(n\log^2n)。