P7592

· · 题解

不妨设 F 为方案数的 GF，用 x 计量点数，用 y 计量 k_1 叉的点数，那么显然

G = x(yG^{k_1} + G^{k_2} + 1)

根据拉格朗日反演

[x^n] G = \frac1n [x^{n-1}] (1+yx^{k_1}+x^{k_2})^n

提取系数

\begin{aligned} [x^{n-1} y^k] (1+yx^{k_1}+x^{k_2})^n &= [x^{n-1} y^k] \sum\limits_{i=0}^n \binom ni (yx^{k_1}+x^{k_2})^i \\ &= \sum\limits_{i=0}^n \binom ni \binom ik [kk_1 + (i-k)k_2 = n-1] \end{aligned}

容易发现使艾佛森括号取到 1 的 i 唯一，直接提取即可。
时间复杂度 O(n)。