首先我来解释一下题目是什么东西，假如给你一个 $k$ 次多项式 $P(x)$，并且已知了 $P(0)$, $P(1)$, $\cdots$, $P(k)$，要求计算出 $P(n), n \in \mathbb N$ 的值，由于已经知道了 $k + 1$ 个点值，那么要插值出系数是可以在 $\mathcal O(k^2)$ 完成，如果使用 FFT 的话是可以在 $\mathcal O(k \log^3 k)$ 的时间内完成的^[1]，但是对于这个特别的问题，我们有一个 $\mathcal O(k)$ 的算法！这好像是杜教先提出来的，然后还有这篇文章

(more…)

Read More

总算是快把 FFT 和生成函数的各种东西补了好多，膜拜策爷的论文和 Picks 的博客 QAQ

这篇文章大概就是说如何用牛顿迭代法来解满足 $G(F(z)) \equiv 0 \pmod {z^n}$ 的 $F(z)$

然后这东西可以比较方便地计算 $\sqrt{A(z)}$、$e^{A(z)}$，也就是多项式开根、求指数对数之类鬼畜的东西，在生成函数计数中十分有用

顺便一提，这里说的“多项式”实际上你可以直接理解为生成函数或者形式幂级数

(more…)

Read More

多项式的多点求值（multi-point evaluation）是给出一个多项式 $A(x)$，和 $n$ 个点 $x_0, x_1, \cdots, x_{n-1}$，要求求出 $A(x_0), A(x_1), \cdots, A(x_{n-1})$

相反的，多项式的插值（interpolation）是给出 $n+1$ 个点 $(x_0, y_0), (x_1, y_1), \cdots, (x_n, y_n)$，求出一个 $n$ 次多项式，使得这些点都在这个多项式上

这两个问题实际上是在多项式的点值表示（point-value representation）和系数表示（coefficient representation）之间转换的方法，在快速傅里叶变换中由于带入值的特殊性质，可以在 $\mathcal O(n\log n)$ 的之间内将两种东西互相转换，但是，如果是任意给定点要求求值或者插值，就没有比较好的性质可以利用，但是仍然有比较快速的方法来计算它们

(more…)

Read More

概述

多项式求逆元是多项式除法和多项式取模的必要过程，在竞赛中，有时候多项式求逆元的应用比多项式的除法还要多，用快速傅里叶变换以及倍增算法可以做到在 $\mathcal O(n\log n)$ 的时间内求出一个多项式的逆元

基本概念

在介绍多项式的逆元之前，先说明一些概念：多项式的度、多项式的逆元、多项式的除法和取余

对于一个多项式 $A(x)$，称其最高项的次数为这个多项式的度（degree），记作 $deg A$

对于多项式 $A(x), B(x)$，存在唯一的 $Q(x), R(x)$ 满足 $A(x) = Q(x)B(x) + R(x)$，其中 $deg R < deg B$，我们称 $Q(x)$ 为 $B(x)$ 除 $A(x)$ 的商，$R(x)$ 为 $B(x)$ 除 $A(x)$ 的余数，可以记作

$$A(x) \equiv R(x) \pmod {B(x)}$$

(more…)

Read More

概述

计算多项式的乘法，或者计算两个大整数的乘法是在计算机中很常见的运算，如果用普通的方法进行，复杂度将会是 $\mathcal O(n^2)$ 的，还有一种分治乘法，可以做到 $\mathcal O(n^{\log_23})$ 时间计算（可以看这里）。下面从计算多项式的乘法出发，介绍快速傅里叶变换（Fast Fourier Transform, FFT）如何在 $\mathcal O(n\log n)$ 的时间内计算出两个多项式的乘积

准备知识

这里介绍一些后面可能会用到的知识（主要是关于多项式、卷积以及复数的），如果你已经知道觉得它太水了或者想用到的时候再看就跳过吧

多项式

简单来说，形如 $a_0+a_1X+a_2X^2+\cdots+a_nX^n$ 的代数表达式叫做多项式，可以记作$P(X)=a_0+a_1X+a_2X^2+\cdots+a_nX^n$，$a_0, a_1, \cdots, a_n$ 叫做多项式的系数，$X$ 是一个不定元，不表示任何值，不定元在多项式中最大项的次数称作多项式的次数

多项式的系数表示法

像刚刚我们提到的那些多项式，都是以系数形式表示的，也就是将 $n$ 次多项式 $A(x)$ 的系数 $a_0, a_1, \cdots, a_n$ 看作 $n+1$ 维向量 $\vec a=(a_0,a_1,\cdots,a_n)$，其系数表示（coefficient representation）就是向量 $\vec a$

多项式的点值表示法

如果选取 $n+1$ 个不同的数 $x_0, x_1, \cdots, x_n$ 对多项式进行求值，得到 $A(x_0), A(x_1), \cdots, A(x_n)$，那么就称 $\{\left(x_i, A(x_i)\right) : 0 \leq i \leq n, i \in \mathbb Z\}$ 为多项式 $A(x)$ 的点值表示（point-value representation）

多项式 $A(x)$ 的点值表示不止一种，你只要选取不同的数就可以得到不同的点值表示，但是任何一种点值表示都能唯一确定一个多项式，为了从点值表示转换成系数表示，可以直接通过插值的方法

复数

后面提到的 $i$，除非作为 $\sum$ 求和的变量，其余的都表示虚数单位 $\sqrt{-1}$

单位根

$n$ 次单位根是指能够满足方程 $z^n=1$ 的复数，这些复数一共有 $n$ 个它们都分布在复平面的单位圆上，并且构成一个正 $n$ 边形，它们把单位圆等分成 $n$ 个部分

根据复数乘法相当于模长相乘，幅角相加就可以知道，$n$ 次单位根的模长一定是 $1$，幅角的 $n$ 倍是 $0$

这样，$n$ 次单位根也就是

$$e^{\frac{2\pi ki}{n}}, k = 0, 1, 2, \cdots, n - 1$$

再根据欧拉公式

$$e^{\theta i}=\cos\theta + i\sin\theta$$

就可以知道 $n$ 次单位根的算术表示

如果记 $\omega_n=e^{\frac{2\pi i}{n}}$，那么 $n$ 次单位根就是 $\omega_n^0, \omega_n^1, \cdots, \omega_n^{n-1}$

多项式的乘法

给定两个多项式 $A(x), B(x)$

$$A(x) = \sum_{i=0}^na_ix^i = a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0 \\ B(x) = \sum_{i=0}^nb_ix^i = b_nx^n+b_{n-1}x^{n-1}+\cdots+b_1x+b_0$$

将这两个多项式相乘得到 $C(x) = \sum_{i=0}^{2n}c_ix^i$，在这里

$$c_i=\sum_{j+k=i,0\leq j,k\leq n}a_jb_kx^i$$

如果一个个去算 $c_i$ 的话，要花费 $\mathcal O(n^2)$ 的时间才可以完成，但是，这是在系数表示下计算的，如果转换成点值表示，知道了 $A(x), B(x)$ 的点值表示后，由于只有 $n+1$ 个点，就可以直接将其相乘，在 $\mathcal O(n)$ 的时间内得到 $C(x)$ 的点值表示

如果能够找到一种有效的方法帮助我们在多项式的点值表示和系数表示之间转换，我们就可以快速地计算多项式的乘法了，快速傅里叶变换就可以做到这一点

(more…)

Read More

是这样的，这几天在写 FFT，由于是在模意义下的，需要各种素数……

然后就打了个表方便以后查了、

如果 $r \cdot 2^k + 1$ 是个素数，那么在$\bmod r \cdot 2^k + 1$意义下，可以处理 $2^k$ 以内规模的数据，

$2281701377=17\cdot 2^{27}+1$ 是一个挺好的数，平方刚好不会爆 long long

$1004535809=479\cdot 2^{21}+1$ 加起来刚好不会爆 int 也不错

还有就是 $998244353=119 \cdot 2^{23}+1$

下面是刚刚打出来的表格（$g$ 是$\bmod (r \cdot 2^k + 1)$的原根）

(more…)

Read More