多项式相关

Problem - E - Codeforces vp 的一场 div1，还没仔细看。有兴趣再补。

1002 一次买够杭电联赛题操作比较接近多项式卷积，但是下标是模素数 P 意义下乘法。模素数 P 必有原根，找出来后把原下标都写成原根的幂次，从而在 $1,2,\cdots,P-1$ 和 $1,2,\cdots,P-1$ 之间建立一个一一映射，就能把乘法变成加法了。还有个经验是可以在计算多项式乘法的时候检验一下非零项数，即其中一个多项式非常稀疏以至于只有两三项的情况，这个时候暴力卷积然后 skip 掉零项反而比跑 ntt 更快。

NTT 模板¶

主要的部分就是算一个特殊的矩阵乘向量得到的向量 void ntt(vector a, bool invert 因为逆矩阵几乎一样，方法通用，就写进一个函数里 ) 记录一下 a 的大小 n。实际上这里的 n 会在后面调用的时候提前变成 2 的幂次。

先作一个预处理，所谓蝴蝶操作。就是后面我们会把系数根据奇偶位分成两份多项式，直到拆到底层成为一个直接可以引用的下标。我们把这个下标提前放好，后面就可以迭代地自下往上了。这里先直观给出小例子

0 → 000 → 000 → 0
1 → 001 → 100 → 4
2 → 010 → 010 → 2
3 → 011 → 110 → 6
4 → 100 → 001 → 1
5 → 101 → 101 → 5
6 → 110 → 011 → 3
7 → 111 → 111 → 7

大致上是一个两两配对并 swap 的过程。我们可以只枚举小的然后去找对应大的，防止 swap 两次结果还原了。只要能做到 $O(n\log n)$ 就行了，这里的实现方法可以是：考虑我给 $i$ 从 $0$ 开始加实际上在干什么：从右往左找到第一个 0，变成 1，然后抹掉这个位置以右的位置。镜面地对另一个 $j$ 从 $0$ 开始操作，就能得到镜面的结果了。

从最短 len=2 开始往 n 合并，每次 len 倍长。假设已经计算出了 $len/2$ 的奇数项多项式和偶数项多项式。现在来计算 len 的多项式。记当前单位根是 $w_{len}$，实质上对于 $f(w_{len}^{k})$，我们需要的是 $f(w_{len}^{k}) = f_1(w_{len/2}^{k}) +w_{len}^{k}f_2(w_{len/2}^{k})$。对于 $k<len/2$ 我们就直接引用对应位置的点值来计算；对于 $k\ge len/2$ 的，考虑到 $w_{len/2}^{k} = w_{len/2}^{k-len/2}$，$w_{len}^{k} = -w_{len}^{k-len/2}$，可以引用对应点值，也可以在在处理 $k-len/2$ 时顺便处理了，并且这样的话就可以直接覆盖掉对应的位置而不怕后面还会被引用了。

模意义下的单位根 $w_{len}$ 是什么意思呢？NTT 模数 $p$ 减一，即 998244353-1 后是 $2^{23}\approx 8e6$ 的倍数，大于算法竞赛环境下 $O(n\log n)$ 复杂度允许的 $n$；$3$ 又是这个模数的原根，即第一个循环节刚好是费马小定理指出的一个循环节 $p-1$，所以我们可以指定 $w_{len} = 3^{(p-1)/len}$，并验证它符合我们需要的各种单位根性质。稍微强调一下：最主要的动机在于 $$ \sum_{k=0}^{n-1}(w_n^{i-j})^{k} $$ 应该需要在 $i=j$ 时为一个统一的常数，而在 $i\not=j$ 时为 $0$，即这时 $$ w_{n}^{i-j}\not= 1 \land w_{n}^{(i-j)n}=1 $$ 加入让 $w_{len}=g^{(p-1)/len}$，其中 $g$ 不是原根的话，$g^{(i-j)(p-1)/n}$，这里 $(i-j)$ 的取值范围实际上是 $-(n-1)$ 到 $(n-1)$，就有可能撞上一个比 $p-1$ 小的循环节，让这个结果变成 $1$ 了。这个动机实质上就是在验证这个形式的矩阵是否真的是逆矩阵。对于原根打底的，那确实是。反之，要么我们通过上面的解剖来验证伪，要么就直接考虑一下矩阵中存在完全相同的某两行，那么行列式为 $0$，必然不存在逆矩阵。

如果是 invert 的话实质上求逆时还会多一项公因数 $1/n$（其实就是我们先前提到的统一常数），所以每项结果再乘一下就好了。