FPS 24题

· · 算法·理论

喜欢多项式/se/se/se
https://atcoder.jp/contests/fps-24

默认读者已经掌握 多项式学习笔记 和 多项式进阶——生成函数 GF 与集合幂级数 中的知识。（如果对本文的某些专有名词感到困惑，可以去这两篇文章找找）

本文中 F 均表示 OGF，\hat F 表示 EGF，f_i 表示 F 的各项系数。

A

[x^n](x+x^3+x^4+x^6)^d

B

[x^n](1+x)(1+x+x^2)\frac1{1-x^2}\frac1{1-x^3}

化简得到 [x^n]\frac1{(1-x)^2}=n+1。

C

[x^s]\left(\frac{1-x^{m+1}}{1-x}\right)^n

D

显然每个数都不相同，所以只需对升序序列计数，答案 \times n! 即可。
对于升序序列，可以考虑他们的差分：

\sum_{k=0}^n[x^k]\frac{1-x^{m+1}}{1-x}\left(\frac x{1-x^2}\right)^{n-1}

E

怎么混入了一个基础背包练习题。

F

\begin{aligned} &\left[\frac{x^n}{n!}\right]\sum_{i}\frac{x^i}{i!}\sum_{j\mid2}\frac{x^j}{j!}\sum_{k\nmid2}\frac{x^k}{k!}\\ =&\left[\frac{x^n}{n!}\right]e^x\frac{e^x+e^{-x}}2\frac{e^x-e^{-x}}2\\ =&\frac14\left[\frac{x^n}{n!}\right]e^{3x}-e^{-x}\\ =&\frac{3^n-(-1)^n}4 \end{aligned}

G

怎么混入了一个进阶背包练习题。

按照 L 分块，预处理前后缀背包，询问的话 merge 两个背包即可。

H

注意到 a\in\{0,1\}，考虑按 x 分阶段算。
当 a=0 时，设此时的生成函数为 F，容易得到：

F=\frac1{1-\frac x{1-x}}=\frac{1-x}{1-2x}

当 a=1 时，设这一步的生成函数为 G，容易得到：

G=\frac{1}{1-x}

答案为 [x^m]F(GF)^n=[x^m]\dfrac{1-x}{(1-2x)^{n+1}}。

I

[x^k]\prod_i^n(1+a_ix)

J

设走到 i 的概率为 f_i，转移为：

f_n=\sum_{i=1}^mf_{n-a_i}

分治 NTT 优化 DP，走到不合法的位置时将 dp 值改为 0 即可。
有一个坑是当前位置会和 n 取 \min，注意一下。

K

设 f_i 表示确定了 p_1\sim p_i 且 i 作为第一个满足 \max(p_1,p_2\dots p_i)=i 的位置，对应的方案数。那么有：

n!=\sum_{i=1}^nf_i(n-i)!

令 g_i=i!，可以得到 G=FG+1 即 F=1-\dfrac1G。

L

限制等价于每个环长不小于 3。
对于单个环，容易得到 \forall i\ge3,f_i=(i-1)!。
把多个环组合起来就是 \exp(\hat F)。

M

原，略。

N

对于价值为 i 的硬币，容易得到生成函数为：

F_i=\frac{1-x^{i(a_i+1)}}{1-x^i}

答案即为 \prod F。

发现这个东西其实就是付公主的背包，于是可以在 O(n\log n) 时间内求得 \sum\ln F。

O

看到树及其 \deg，考虑 prufer 序。那么得到，每个点在 prufer 序中必须出现 0 或质数次。（1 号点需要特判）

设 P 表示素数组成的多项式，即：

P=\sum\limits_{i=0\operatorname{or}i\in\texttt{prime}}x^i

则 2\sim n 的贡献为 (\hat P)^{n-1}。

P

f(x)=\sum_{i=0}^kx^{n-i}

所求即为 f(1),f(2)\dots f(m)，多项式多点求值即可。

Q

先把期望转为总和。

f_d=\sum_{i=1}^na_i^d\\g_d=\sum_{i=1}^mb_i^d\\\hat{Ans}=\hat F\times\hat G

接下来考虑如何计算 F,G。这两个是等价的，以 F 为例：

F=\sum_{i=1}^n\sum_{j=1}(a_ix)^j=\sum_{i=1}^n\frac1{1-a_ix}

分治 NTT 即可。

R

一般的 dp 为 f_{i,j}=\frac12(f_{i-1,j-1}+f_{i-1,j+1})，但是最左侧与最右侧很讨厌。尝试通过一些手法使得左右端点可以相同转移，容易想到镜像法。具体来说，将序列扩充为 0,1\dots2^n-1,2^n,2^n-1\dots2,1（将下标平移了），将首尾连成一个环。此时，每个元素的 dp 值都可以由相邻元素的平均值得到。

于是 F_0=1,F_i=\frac12F_{i-1}(x+\frac1x)，答案即为 [x^X]F_T。注意到我们所需的是循环卷积，而本题特意保证了项数是 2 的幂次，于是 \bmod(2^{n+1}-1) 可以在 O(n\log n) 的复杂度内解决。

S

首先明确树上博弈的必胜条件。显然树是一个二分图，于是先手必胜当且仅当初始点位于每一个最大匹配中（有一个坑是这道题询问的是 Alice 必胜，为后手）。那么 type=1 等价于判断 1 号点是否可以不在最大匹配中，type=2 等价于判断是否存在点可以不在最大匹配中。

type=1

设 A 表示 Alice 必胜的 GF，B 表示 Bob 必胜的 GF。（都是在有根树中，因为本题限定根节点为 1，答案 \times\frac1n 即可）

A=x\exp B\\B=x\exp(A+B)-A

消元，得到关于 B 的等式：

B=x(\exp(x\exp B+B)-\exp B)

牛顿迭代即可做到单 \log 复杂度。

type=2

其实是诈骗。注意到问题等价于判断是否存在完美匹配，而对于一棵树如果存在完美匹配的话匹配方式唯一。
于是可以先生成一个完美匹配，方案数 \dfrac{n!}{(\frac n2)!2^{\frac n2}}，然后把这些大小为 2 的联通块连起来，方案数 2^{\frac n2}n^{\frac n2-2}。

T

对于一个颜色序列 c_0=1,c_1\dots c_{T-1},c_T=1，其贡献为 \prod\limits_{i=1}^{T-1}a_{c_i}。现在需要对所有可能的颜色序列求和。

考虑容斥。首先明确，一共有 T 个相邻位置，如果钦定有 cnt 个相邻位置的颜色一样，则容斥系数为 (-1)^{cnt}。
显然开头结尾比较特殊（颜色已经确定且不带权），先考虑较为普通的中间段（一段内部的颜色相同）。容易写出其生成函数为：

F=\sum_{i=1}^n\frac{a_ix}{1+a_ix}

加上开头结尾的贡献，于是答案为：

a_1^{T-1}\times(-1)^T+[x^{T-1}]\frac{(\frac1{1+a_1x})^2}{1-F}

生成函数的分子是在枚举开头结尾段的长度，但是发现这样会忘记钦定 cnt=T，于是在前面补上。

问题在于 T 太大了，不能直接多项式求逆做。化简，发现可以写成 \frac QP，其中 Q 是一个 n 次式，P 是一个 n+2 次式。于是这等价于一个 n+2 阶线性递推，上一个模板即可。

注：请注意线性递推部分的常数，建议使用 EI 文章中的新·线性递推。本人使用的是老算法，即快速幂 + 多项式取模，一个卡常技巧是注意到模数是不变的，可以把多项式取模模板中只关于模数的部分预处理（主要是多项式求逆）。

U

难点在于写出一份 O(n^2) 的暴（正）力（解）。

考虑如何判定一个方案是否可行——扫描每一个时间段，如果该段被覆盖了 >2 次则非法。充要性较为显然，此处不再证明。于是可以 f_{i,j,0/1/2} 表示扫描到了第 i 时间段，已经用过了 j 个区间，目前有多少个区间覆盖当前时间段。转移是 O(1) 的，如果从大到小扫描 j 的话，还可以把 i 删掉。

看到后面的 0/1/2，容易联想到矩阵乘法，发现每次转移的矩阵相同：（把 j 当做多项式中的次数）

\begin{bmatrix}F_{i,0}&F_{i,1}&F_{i,2}\end{bmatrix}\times\begin{bmatrix}1&x&\frac{x^2}2\\0&1&x\\0&0&1\end{bmatrix}\times\begin{bmatrix}1&0&0\\1&1&0\\1&2&1\end{bmatrix}=\begin{bmatrix}F_{i+1,0}&F_{i+1,1}&F_{i+1,2}\end{bmatrix}

分治 NTT 维护矩阵乘法即可。这是因为一个时间段最多让 x 的次数增加 2，而我们只需要 [x^n] 的值，因此我们只需要保留 O(2\times len) 的项数。
题解区有线性做法，大概是只保留末尾的 O(1) 项进行转移。

【另解】
注意到这是一个大小 3\times3，且每个元素都是一个多项式的矩阵乘法。并且由于外层套一个分治 NTT，能够感觉到这道题是一个超大常 O(n\log^2n)，这也是为何在数据范围并不大的情况下本题的时间限制为 12s。合理猜测，一份小常 O(n^2) 代码并不会劣于该算法，于是对暴力 DP 稍加卡常即可通过。
AC 记录：https://atcoder.jp/contests/fps-24/submissions/70703973。

V

感觉官方题解写得很清晰啊，抄一下。

显然坐标不能只用整数表示，需要扩域到 \frac{\sqrt3}2 上，于是不妨设当前坐标为 (\frac{a+\sqrt3b}2,\frac{c+\sqrt3d}2)，用 x^ay^bz^cs^d 表示。那么所求可以写成：

[x^{2H}y^0z^{2W}s^0]\left(x^2+x^{-2}+z^2+z^{-2}+(x+x^{-1})(s+s^{-1})+(y+y^{-1})(z+z^{-1})\right)^n

这东西同时出现了二次项和一次项，考虑用我们小学一年级就学过的方法全部转化为一次。设 X=x+x^{-1}，其余各项同理：

(X^2-2+Z^2-2+XS+YZ)^n=(X(X+S)+Z(Z+Y)-4)^n

这两部分独立，只需解决 [x^{2H}s^0](X(X+S))^k，即可轻松解决原问题。
令 x=pq,s=\frac pq，简单推下式子：

\begin{aligned} &[x^{2H}s^0]((x+x^{-1})(x+x^{-1}+s+s^{-1}))^k\\ =&[p^{2H}q^{2H}]((pq+(pq)^{-1})(pq+(pq)^{-1}+pq^{-1}+p^{-1}q))^k\\ =&[p^{2H}q^{2H}](pq+(pq)^{-1})^k(p+p^{-1})^k(q+q^{-1})^k\\ =&\sum_{i=0}^k\binom ki\binom k{H-i+k}^2 \end{aligned}

于是可以通过一次卷积求出 k=0\sim n 上述问题的答案。

W

不太会啊……

X

不太会啊……