FPS 24题

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

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

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

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

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

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

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

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

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

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

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

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

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

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

原，略。

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

答案即为 $\prod F$。

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

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

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

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

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

先把期望转为总和。

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

分治 NTT 即可。

一般的 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)$ 的复杂度内解决。

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

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

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

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

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

对于一个颜色序列 $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}$。
显然开头结尾比较特殊（颜色已经确定且不带权），先考虑较为普通的中间段（一段内部的颜色相同）。容易写出其生成函数为：

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

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

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

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

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

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

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

分治 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。

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

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

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

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

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

不太会啊……

不太会啊……