FPS24 简要题解

· · 题解

脑子转得太慢，被严肃击杀了。来补一篇简要题解。

A

\text{ans}=[x^N](x+x^3+x^4+x^6)^D

B

\text{ans}=[x^N]\frac{(1+x)(1+x+x^2)}{(1-x^2)(1-x^3)}=N+1

C

\text{ans}=[x^S]\left( \frac{1-x^{M+1}}{1-x}\right)^N

D

\text{ans}=N![x^M]\frac{1}{(1-x)^2}\left(\frac{x}{1-x^2} \right)^{N-1}

E

\text{ans} = N![x^N]\prod_{i=1}^M \left( \sum_{j=0}^i \frac{x^j}{j!}\right)

F

\text{ans}=\frac{N!}{4}[x^N](\text e^x+\text e^{-x})(\text e^x-\text e^{-x})\text e^x=\frac{3^N-(-1)^N}{4}

G

\text{ans}_m=[x^N]f_m(x)=[x^N]\prod_{i=m}^{m+L-1}\frac{1}{1-x^i}

递推维护 f_m(x)，从 m 推到 m+1 的时间复杂度是 \Theta(N)。

H

\text{ans}=[x^Ny^M]\frac{1}{1-\frac{x+y}{1-y}}=[x^N y^M] \frac{1-y}{1-x-2y}

其中 [x^N y^M] (1-x-2y)^{-1}=\binom{N+M}{N} 2^M。

I

\text{ans}=[x^K]\prod_{i=1}^N(1+A_ix)

J

朴素的 DP 就和线性递推很像，只不过钦定了 B_i 位置为零。
直接处理比较困难，但若使用分治 FFT，则只需要在递归到底层时，将 B_i 位置强行设为 0 即可。

K

将排列按前缀 max 等于下标的位置分段，或查询 OEIS 可知所有排列都可以由这种段拼接而成，故

\text{ans}=-[x^N] \left( \sum_{i \geq 0} i! x^i\right)^{-1}

L

视排列为置换，即其中不含有长度为 1,2 的轮换环，故

\text{ans}=N! [x^N] \exp \left( \sum_{i \geq 3} \frac{x^i}{i}\right)=N![x^N] \frac{\exp(-x-x^2/2)}{1-x}

M

P4841：

\text{ans}=N! [x^N] \ln \left( \sum_{i \geq 0}\frac{2^{i(i-1)/2}}{i!}x^i\right)

N

P4389：

\text{ans} = [x^N] \prod_{1=1}^N \frac{1-x^{i(A_i+1)}}{1-x^i}

O

设答案的 EGF 为 F(x)，\mathbb P 为质数集，则

F(x) = x \left( 1+\sum_{i \in \mathbb P} \frac{F(x)^i}{i!}\right)

由 Lagrange 反演可知

\text{ans}=\frac 1n[x^{n-1}] \left(1+\sum_{i\in \mathbb P}\frac{x^i}{i!} \right)^n

P

\text{ans}_m = \sum_{i=0}^K \binom Ni m^{N-i}

多点求值即可。

Q

题意同 P4705，可参考个人早期题解。

R

令 n=2^N，并将节点编号改为从 0 开始。

设 [z^m]f_k(z) 表示走 m 步刚好到 k 位置的概率，根据 f_k(z) = (z/2)(f_{k-1}(z)+f_{k+1}(z)) \ \ (2 \leq k \leq n-2)，结合线性递推的通项公式，可以将 f_n(z),f_{n-1}(z) 都用 f_0(z) 表示（注意边界处的方程会有所不同），然后可以解出 f_0(z)，进一步得到 f_k(z)。

在解线性递推通项时，会得到两个特征根，选取最低非零项为 1 次的那个根，在计算 [z^T] f_k(z) 时使用另类 Lagrange 反演即得

[z^T]f_k(z)=\frac{1}{2^{T-1}}[z^T]\frac{(1+z^2)^T (z^k+ z^{2n-k})}{1-z^{2n}} \ \ (1 \leq k < n)

（以上推导较为复杂，均使用 Mathematica 完成）
对于 k=n 或 k=0 的边界情况，答案需要再除以 2。

S

$$F(x)=x \exp G(x) \ , \ G(x)=x (\exp F(x)-1)\exp G(x)$$ 代换一下即得只含 $G(x)$ 的方程，牛顿迭代求解即可，$\text{ans}_n = (n-1)! [x^n] x \exp G(x)$。 $\text{type}=2$ 怎么还要组合意义？ 后手必胜当且仅当树存在完美匹配。 - 此时无论先手如何操作，后手都能沿着完美匹配的边移动。 - 否则，只需考虑树的最大匹配，先手选择不在匹配中的点开始。此时后手只能将其移动到被匹配的点，而先手也只需沿着匹配边移动即可获胜。 设 $F(x)$ 为存在完美匹配的有根树 EGF，$G(x)$ 为除根以外所有点都被匹配的树的 EGF，则有方程 $$F(x)= x G(x) \exp F(x) \ , G(x)=x\exp F(x)$$ 可以得到 $F(x)=x^2\exp (2 F(x))$，使用 Lagrange 反演（注意 $F(x)$ 没有奇数次项）即得 $$[x^{2n}]F(x)=\frac 1n[x^{n-1}](\text e^{2x})^n=\frac{(2n)^{n-1}}{n!}$$ ### T 类似 **R** 题，设 $[z^m]f_k(z)$ 表示移动 $m$ 次后落在颜色 $k$ 上的方案数，可以得到 $$f_k(z)=[k=1]+z A_k\sum_{i=1}^n [i \neq k] f_i(z) $$ 设 $S(z)=\sum_k f_k(z)$，则算出 $S(z)$ 后可以根据上式直接得到 $f_k(z)$。设 $B=\sum_k A_k$，再将上式对 $k$ 求和得到 $$S(z)=1+\sum_{i=1}^n \frac{[i=1]+z A_i S(z)}{1+zA_i}(B-A_i)z$$ $$\left( 1-z^2 \sum_{i=1}^n \frac{A_i(B-A_i)}{1+A_i z}\right)S(z) = \frac{1+B z}{1+A_1 z}$$ 分治合并分式即可得到 $S(z)$ 的有理分式表示，也就能进一步算出答案为 $[z^T]f_1(z)/A_1$。 ### U 经过一些转化可以的得到一个用矩阵描述的朴素 DP，求其特征多项式后可以用二元 GF 表达： $$\text{ans}=N! [x^N] \frac{2 (1-t)^2-4 t x}{(1-t) \left(2(1-t)^2-6tx-tx^2\right)}$$ （得到的关于 $t$ 的幂级数即为答案的 GF） 因为二元有理分式的一行必然是常数阶微分有限的，故答案序列也是常数阶整式递推的。可以做到 $\Theta(U)$ 的复杂度。 ### V $12$ 个方向的向量都可以表示为 $(a+b\sqrt 3,c+d\sqrt 3)/2$ 的形式，其中 $a,b,c,d$ 均为 $0,1,-1$ 中的一个。于是答案可以用四维的 GF 表示。 答案即为 $$[a^{2H}b^0 c^{2W}d^0] (a^2+a^{-2}+c^2+c^{-2}+(a+a^{-1})(d+d^{-1})+(b+b^{-1})(c+c^{-1}))^N$$ ~~我们猜测答案关于 $N$ 整式递推，故高斯消元即可。~~ 好吧还是稍微说一下，大力展开多项式可得其为 $$[a^{2H} c^{2W}]\sum_{i+j+k=N}\binom{N}{i,j,k}(a^2+a^{-2}+c^2+c^{-2})^i (a+a^{-1})^j (c+c^{-1})^k ([b^0] (b+b^{-1})^k) ([d^0] (d+d^{-1})^j)$$ 设 $$F(z)=[a^H] \exp((a+a^{-1})z)\sum_{i \geq 0} \frac{(a+a^{-1}+2)^iz^{2i}}{(i!)^2}$$ 类似地设 $G(z)$，则答案为 $N! [z^N]F(z)G(z)$。 $$\begin{aligned}k![z^k] F(z) &=\frac{1}{k!}[a^H]\sum_i \binom{k}{2i}\binom{2i}{i}(a+a^{-1}+2)^i (a+a^{-1}+2-2)^{k-2i} \\ &=\frac{1}{k!}\sum_i \binom{k}{2i}\binom{2i}{i} \sum_{j=0}^{k-2i}\binom{k-2i}{j}(-2)^j \binom{2(k-i-j)}{H+k-i-j} \\ &= \sum_j \frac{(-2)^{k-j}}{(k-j)!}\sum_{i=0}^j \frac{1}{(j-2i)! (i!)^2} \binom{2(j-i)}{H+(j-i)}\end{aligned}$$ 现在内层和式与 $k$ 无关，可以设其为 $v_j$。可以发现 $v_j$ 是常数阶整式递推的，但要注意 $j<H$ 时时 $v_j=0$，高斯消元找递推式要从第 $H$ 项开始。当然也可以直接卷积计算： $$v_j=\frac{1}{j!}\sum_{i=0}^j \binom ji ^2\binom{j}{i+H}$$ :::info[简要证明] 我们要证明的是 $$\sum_{i=0}^j\binom{j}{2i}\binom{2i}{i} \binom{2(j-i)}{H+(j-i)}=\sum_{i=0}^j \binom ji ^2\binom{j}{i+H}$$ 对 $H$ 建立 GF 即为 $$\begin{aligned}\sum_{i=0}^j \binom{j}{2i}\binom{2i}{i} \frac{(1+s)^{2(j-i)}}{s^{j-i}}&=\sum_{i=0}^j \binom ji^2 \frac{(1+s)^j}{s^i} \\ (1+s)^j\sum_{i=0}^j \binom{j}{2i}\binom{2i}{i} \frac{s^i}{(1+s)^{2i}}&=\sum_{i=0}^j \binom ji^2 s^i\end{aligned}$$ 再对 $j$ 建立 GF，则我们只需要证明 $$\sum_{j=0}^\infty t^j \sum_{i=0}^j \binom ji^2 s^i=\frac{1}{1-t(1+s)}\left( 1-\frac{4t^2 s}{(1-t(1+s))^2}\right)^{-1/2}$$ 这个就是经典结论了，在 OEIS 上就能直接找到。具体操作方法可以用提取对角线法，或[逆用 Lagrange 反演](https://www.luogu.com/article/yz06qxxj)。 ::: ### W 不是说好的 FPS 场吗，怎么有集合幂级数题，这我真不熟啊。 ~~先留个坑。~~ 也不知道什么时候会补。 ### X 我们伟大的[飞雨烟雁](https://www.luogu.com.cn/user/375984)老师早在一年前就给出了这个问题的 $\Theta(n \log^3 n)$ 做法，比 std 更优。具体可以参考他的[专栏文章](https://www.luogu.com.cn/article/y7ydytp2)。此处不再赘述。