2023.12.19

有点太安静了，于是拿耳机听歌写题了（

好像还不错，梦幻联动而且确实挺好听。

P7325 [WC2021] 斐波那契

一开始没看数据范围，以为 \(m\) 很大，想半天然后突然意识到数据范围，呃呃。写了个试试，啥，咋就直接过了。

首先有皮那啥周期，所以循环节是 \(O(m)\) 的，我们只需要考虑这 \(O(m)\) 项里面有没有 \(0\)。

但是状态太多了，你不能 \(O(m^2)\) 枚举所有点对吧。考虑减少点有用数对。

注意到问什么时候有 \(0\)，那么我们给整个序列乘一个数这个答案是不变的。那么我们可以考虑乘个逆元把 \(a\) 或者 \(b\) 变成 \(1\)。

但是问题是万一逆元都不存在呢？这时候 \(\gcd(a, b, m) = w > 1\)，我们可以把三个值全除以 \(w\) 就行了。容易发现这个操作只需要最开始来一次就够了。

那么每次将 \(a/b\) 变成 \(1\)，这样就只剩下 \(O(m)\) 对值了，而不同的模数只有 \(d(m)\) 种，每种模数的状态和就是因数和，于是总复杂度就是 \(O(\sigma(m) \log m)\)，\(\log\) 是求逆元的复杂度。

题解做法咋都这么麻烦？？

P8354 [SDOI/SXOI2022] 多边形

怎么题单里有个 GF 题。

考虑这个题实际上是加了一些限制的三角剖分，没有限制的三角剖分是卡特兰数 \(C_{n-2}\)，而这里的具体限制是：可以将同一边中的多个边合并起来，然后要求同一边之间不能有连边。

合并过程直接枚举合并成几段，然后组合数算一下，那么考虑同一边不能有连边咋整。

考虑容斥，我们以同一边连边的数量容斥，仔细推一下发现我们只用统计只跨过两条边的不合法集合，因为如果有跨过更多边的不合法边，那么这条不合法边里面连的边都是不合法的，而把这个集合内的容斥系数加和等于 \(0\)。

那么问题就是，可以在同一边选若干跨过两条边的不合法边，然后再乘上里面三角剖分的方案数。我们只需要考虑求出每种内部多边形边数的容斥系数之和即可计算答案，而显然每一边的容斥系数是独立的，我们可以先求出每一边然后再分治乘法乘起来。

现在只考虑一边，我们的问题是：现在有 \(n\) 条边，将若干条边缩起来，然后将剩下的边划分成长度为 \(1\) 或 \(2\) 的段，每个 \(2\) 的容斥系数是 \(-1\)，对每种段数求所有容斥系数之和。

接下来是互动博客，请选择你的路线：

我们可以把两步操作合起来去做，因为实际上我们可以看做先划分 \(1\) 或 \(2\) 段，然后在中间接着划分缩起来的边，那么设 \(f_{i, 0/1/2}\) 表示第 \(i\) 条边在 \(1\) 段，还是在 \(2\) 段的前一部分或后一部分，可以无脑矩阵快速幂，这里比较有趣的是矩阵快速幂的复杂度是 \(O(n \log n)\) 的而不是两个 \(\log\)，因为矩阵没有被取模，这个过程相当于倍增。或者你把 DP 写成更好倍增的形式，都行吧。

哦 dottle 说 9 倍就会 TLE，没事了，其实存在 8 倍的 DP，摆了。

考虑推下式子：先枚举划分成多少段，然后枚举选几段 \(2\)，设这边一共有 \(n\) 条边，那么容易发现我们就是要求：

\[\begin{aligned} F_n(x) &= \sum_{i=0}^{n} \binom{n - 1}{i - 1} \sum_{j=0}^i \binom{i - 2j + j}{j} (-1)^j x^{i - 2j + j}\\ &=\sum_{i=0}^{n} \binom{n - 1}{i - 1} \sum_{j=0}^i \binom{i - j}{j} (-1)^j x^{i - j}\\ &=\sum_{k=0}^n x^k \sum_{i=0}^{n} \binom{n - 1}{n - i} \binom{k}{i - k} (-1)^{i - k}\\ \end{aligned} \]

也就是说，我们要求出一个数组 \(f_k = \sum_{i=0}^{n} \binom{n - 1}{n - i} \binom{k}{i - k} (-1)^{i - k}\)。但是我们迎来了 \(i, k - i, i + k\) 三个下标，没法直接卷积了，哈哈！

组合意义的尽头是代数推导。

考虑拿 GF 刻画一下，引入个元 \(x\)，将上式写成 \(n-i\) 与 \(i-k\) 的卷积形式，即：

\[f_k = [x^{n - k}] (1+x)^{n-1} (1-x)^k \]

这下长得足够抽象了，请选择你的路线：

大力莽一下，记 \(G_k(x) = (1+x)^{n-1} (1-x)^k\)，求个导得：

\[\begin{aligned} G'_k(x) &= G_k(x) \left(\frac{n-1}{1+x} - \frac{k}{1-x}\right)\\ (1-x^2) G_k'(x) &= (n-1-k) G_k(x) - (n-1+k) x G_k(x)\\ (i+1) g_{k,i+1} &= (n - 1 - k) g_{k,i} - (k + n - i) g_{k,i-1}\\ \end{aligned} \]

然后还有 \(G_{k+1}(x) = G_k(x) (1-x)\)，所以有 \(g_{k+1,i} = g_{k, i} - g_{k,i-1}\)。

那你要求的是 \(g_{k,n-k}\)，你就可以 \(O(n)\) 递推了。

有 \(f_k = [x^n] (1+x)^{n-1} (x-x^2)^k\)，拆一下有 \(f_k = \sum_{i=0}^n [x^{n-i}] (1+x)^{n-1} [x^i] (x-x^2)^k\)，记 \(g_i = [x^{n-i}] (1+x)^{n-1}\)，那么就是 \(f_k = \sum_{i=0}^n g_i [x^i] (x-x^2)^k\)。

转置一下，考虑求 \(g_i = \sum_{k=0}^n f_k [x^i] (x-x^2)^k\) 的算法，发现这就是在求多项式 \(F(x-x^2)\)，那么就拆一下，有 \(F(x-x^2) = F(-(x-\frac 12)^2 + \frac 14)\)，那么有流程：

\(F(x) \gets F(x + \frac 14)\)；
\(F(x) \gets F(-x)\)；
\(F(x) \gets F(x^2)\)；
\(F(x) \gets F(x - \frac 12)\)。

于是转置过来做就可以了，复杂度 \(O(n \log n)\)。

因为我第一次学转置原理，所以需要写一下多项式平移咋转置（

首先多项式平移实际上是：

\[F(x+b) = \sum_{i=0}^n \frac{x^i}{i!} \sum_{j=0}^n j! f_j \frac{b^{j-i}}{(j-i)!} \]

令 \(G(x) = \sum \frac{b^i}{i!} x^i\)，那么上述过程可以看做是：

将 \(F(x)\) 的各项系数乘 \(i!\)；
\(F(x) \gets F(x) \times^T G(x)\)；
将 \(F(x)\) 的各项系数除以 \(i!\)。

那么转置就是先除以 \(i!\)，然后正常乘一个 \(G(x)\)，然后再将系数乘 \(i!\)。

考虑直接大力 GF 表示答案，考虑每一段要不然是一段，要不然是两段拼起来的，一端的系数 GF 就是 \(\frac{w}{1-w} - (\frac{w}{1-w})^2 = \frac{w(1-2w)}{(1-w)^2}\)，那么答案 GF 就是 \(\sum_{k\ge 0} x^k [w^n] \left(\frac{w(1-2w)}{(1-w)^2}\right)^k\)。

请选择你的路线：

无所谓，我是无脑选手。把上面的式子直接写成二元 GF 的形式，要求的就是 \([w^n] \frac{1-2x+x^2}{1-(x+2)w+(1+2x)w^2}\)，可以无脑 Bostan-Mori 求，每次需要 8 次多项式乘法。

dottle：实测 9 次会 T，8 次可以。

直接拉反，令 \(u\) 为 \(\frac{w(1-2w)}{(1-w)^2}\) 的复合逆，那么有：

\[[w^n] \left(\frac{w(1-2w)}{(1-w)^2}\right)^k = \frac{k}{n} [x^{n-k}] \left(\frac{x}{u}\right)^n \]

可以直接暴力全家桶求出来，或者 ODE 线性求出来。