自动搬运

查看原文

来自洛谷，原作者为

	Aleph1022 「笑可以天然地飘洒 心是一地草野 唯一的家乡」

搬运于2025-08-24 22:31:21，当前版本为作者最后更新于2021-05-05 14:28:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

不妨设 $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)$。