SCCPC2025 E/G 更优做法

· · 个人记录

首先我没去，被报名只是给学弟凑满三个人用的，只是看了网上的题面。

E

首先有大小为 k 的环的竞赛图等价于存在 SCC 大小 \geq k，只用计数所有 SCC 大小 <k 的有标号竞赛图。

首先注意到有标号强连通竞赛图是经典问题洛谷有原题，可以直接对一般竞赛图的 EGF 反着推一下 SEQ，也是一个求逆。

然后容易得到了大小 <k 的竞赛 SCC 的 EGF，然后再 SEQ 一下就行了。

时间 O(n\log n)，幽默要用分治 FFT。

为啥场上没人过？

G

后面的计算都是在模意义下的。

题目要求相当于 AX=t，A 是范德蒙德矩阵，t 是 t^i 的向量，X 是答案构成的向量。

直接对范德蒙德矩阵求逆，于是我们现在要求：X=A^{-1}t，就是要计算 x_i=\frac{1}{n}\sum\limits_{j=0}^{n-1} \frac{t^{j}}{a_{j+1}^{i}}，你发现还是做不了快于 n^2。

考虑转置原理，我们发现我们只用解决转置问题，X^{\prime}=(A^{-1})^{T}t，发现现在要求 x_i=\frac{1}{n}\sum\limits_{j=0}^{n-1} \frac{t^j}{a_{i}^{j}}。

相当于对 i=0\sim n-1 求 \sum\limits_{j=1}^{n} b_j^i，发现这就是 P7431 [THUPC 2017] 小 L 的计算题，可以分治+FFT 做到 O(n\log^2n)，转置这个做法即可得到我们的答案。

我不是完全懂转置原理的实现，所以不会改写算法，应该没啥问题？

有趣的是我们不求逆直接转置矩阵的话发现就是一个多项式快速插值的问题，于是出题人的做法本质上解决了一个转置后的多项式快速插值，那他点值全部都是 t^i 的意义只是方便他不用转置原理而是奇怪地用线代做是不是太抽象了？