多项式与生成函数 学习笔记

拉格朗日插值

给出 $n$ 个点 $(x_i,y_i)$，求出过这 $n$ 个点的 $n-1$ 次多项式 $L(x)$。

拉格朗日插值多项式：

$$L(x)=\sum_{i=0}^n\frac{\prod_{j\ne i}(x-x_j)}{\prod_{j\ne i}(x_i-x_j)}\cdot y_i$$

时间复杂度 $O(n^2)$。

---

快速傅里叶变换 FFT

单位根

定义：$\omega_n=e^{\frac{2\pi i}n}=\cos(\frac{2\pi}n)+i\cdot\sin(\frac{2\pi}n)$。

两个复数相乘，模长相乘，幅角相加。

性质：

1. $\omega_{2n}^{n+k}=-\omega_{2n}^k$
2. $\omega_{2n}^{2n+k}=\omega_{2n}^k$
3. $\omega_{mn}^{mk}=\omega_n^k$

点值序列

一个 $n$ 次多项式可以由 $n+1$ 个点确定。

而将 $f\times g$ 可以由 $f$ 的 $2n+1$ 个点和 $g$ 的 $2n+1$ 个点对应相乘得到。

快速系数转点值 DFT

$$\begin{aligned} f\left(\omega_n^k\right)&=a_0+a_1\omega_n^k+a_2\omega_n^{2k}+\cdots+a_{n-1}\omega_n^{(n-1)k}\\ &=a_0+a_2\omega_n^{2k}+\cdots+a_{n-2}\omega_n^{(n-2)k}+a_1\omega_n^k+a_3\omega_n^{3k}+\cdots+a_{n-1}\omega_n^{(n-1)k}\\ &=a_0+a_2\omega_{n/2}^{2k}+\cdots+a_{n-2}\omega_{n/2}^{(n-2)k}+\omega_n^k\left(a_1+a_3\omega_{n/2}^{2k}+\cdots+a_{n-1}\omega_{n/2}^{(n-2)k}\right)\\ \end{aligned}$$

故可以拆成奇偶两部分，偶在左，奇在右。将两部分分别处理完后，可以合并为：

$$\begin{cases} f\left(\omega_n^k\right)&=g_0\left(\omega_{n/2}^k\right)+\omega_n^k\cdot g_1\left(\omega_{n/2}^k\right)\\ f\left(\omega_n^{k+(n/2)}\right)&=g_0\left(\omega_{n/2}^k\right)-\omega_n^k\cdot g_1\left(\omega_{n/2}^k\right) \end{cases}$$

第二个式子的符号是 $+(n/2)$ 来的。

快速点值转系数 IDFT

将上式 $\omega_n^k$ 前的符号取反一下即可。最后记得再 $\div n$。

非递归版本

考虑位逆序置换（蝴蝶变换），$0,1,2,3,4,5,6,7$ 会变换成 $0,4,2,6,1,5,3,7$。即翻转 $i$ 的二进制表示后即为最终位置的下标。

定义 $c(i)$ 表示 $i$ 的翻转二进制表示。它等于 $c\left(\lfloor\frac i2\rfloor\right)$ 右移一位后补上最高位。

typedef double db;
typedef std::complex<db> comp;
const db PI = acos(-1.0);
const int N = 3e6 + 7;
void DFT(comp* f, int n, int rev) {  // 1: 正变换，-1: 逆变换
    static int c[N];
    static comp tmp[N];
    for (int i = 0; i < n; i++) tmp[i] = f[i];
    for (int i = 0; i < n; i++) f[i] = tmp[c[i] = (c[i / 2] / 2) | ((i & 1) ? (n / 2) : 0)];
    for (int l = 2; l <= n; l *= 2) {
        comp step(cos(2 * PI / l), sin(2 * PI / l * rev));
        for (int i = 0; i + l <= n; i += l) {
            comp cur(1, 0);
            for (int k = i; k < i + l / 2; k++, cur *= step)
                tmp[k] = f[k] + cur * f[k + l / 2], tmp[k + l / 2] = f[k] - cur * f[k + l / 2];
        }
        for (int i = 0; i < n; i++) f[i] = tmp[i];
    }
}

---

快速数论变换 NTT [UNFINISHED]

原根有着和单位根相似的性质。要求模数形如 $q\times2^k+1$，NTT 模数表。

---

快速莫比乌斯变换 FMT

求 $c_i=\sum\limits_{j~\text{and}~k=i}a_jb_k$。

对于集合幂级数 $f$，定义 $f'$：$f'_S=\sum_{S\subseteq T}f_T$。即 $S$ 所有超集之和。等价于高维后缀和。

于是上式变为了：

$$\begin{aligned} c'_S&=\sum_{S\subseteq T}\sum_{P\cap Q=T}a_P\cdot b_Q\\ &=\sum_{S\subseteq P}a_P\sum_{S\subseteq Q}b_Q\\ &=a'_p\cdot b'_Q \end{aligned}$$

求出 $c'_S$ 后，高维差分得到 $c_S$。

求 $c_i=\sum\limits_{j~\text{or}~k=i}a_jb_k$，把后缀和改为前缀和即可。

void Or(int n, LL* a, bool rev) {  // 0: 正变换，1: 逆变换
    for (int i = 0; i < n; i++)
        for (int j = 0; j < (1 << n); j++)
            if (j & (1 << i)) {
                a[j] += (rev ? mod - a[j - (1 << i)] : a[j - (1 << i)]);
                if (a[j] >= mod) a[j] -= mod;
            }
}
void And(int n, LL* a, bool rev) {  // 0: 正变换，1: 逆变换
    for (int i = 0; i < n; i++)
        for (int j = (1 << n) - 1; ~j; j--)
            if (!(j & (1 << i))) {
                a[j] += (rev ? mod - a[j | (1 << i)] : a[j | (1 << i)]);
                if (a[j] >= mod) a[j] -= mod;
            }
}

---

快速沃尔什变换 FWT

求 $c_i=\sum\limits_{j~\text{xor}~k=i}a_jb_k$。

对称差：$A\Delta B=\{x|x\in A\cup B,x\not\in A\cap B\}$。

对于集合幂级数 $f$，定义 $f'$：$f'_S=\sum_Tf_T\cdot(-1)^{|S\cap T|}$。

推一推：

$$\begin{aligned} c'_S&=\sum_T(-1)^{|S\cap T|}\sum_{P\Delta Q=S}a_P\cdot b_Q\\ &=\sum_Pa_P\sum_Qb_Q\cdot(-1)^{|(P\Delta Q)\cap T|}\\ &=\sum_Pa_P\cdot(-1)^{|P\cap T|}\sum_Qb_Q\cdot(-1)^{|Q\cap T|}\\ &=a'_P\cdot b'_Q \end{aligned}$$

问题变成了如何求 $a'_S$ 和 $b'_S$。

类似 FFT 地，我们按照是否含有第 $n-1$ 个元素，将所有下标分为 $0\sim 2^{n-1}-1$ 和 $2^{n-1}\sim2^n-1$。假设左部递归出来为 $g_{0,S}=\sum_{0\le T<2^{n-1}}f_T\cdot(-1)^{|S\cap T|}$，右部递归出来为 $g_{1,S}=\sum_{2^{n-1}\le T<2^n}f_T\cdot(-1)^{|S\cap T|-1}$。$-1$ 是因为去掉了第 $n-1$ 个元素。

推一下左部的表达式：

$$\begin{aligned} f'_{0,S}&=\sum_{0\le T<2^n}f_T\cdot(-1)^{|S\cap T|}\\ &=\sum_{0\le T<2^{n-1}}f_T\cdot(-1)^{|S\cap T|}+\sum_{2^{n-1}\le T<2^n}f_T\cdot(-1)^{|S\cap T|}\\ &=\sum_{0\le T<2^{n-1}}f_T\cdot(-1)^{|S\cap T|}+\sum_{2^{n-1}\le T<2^n}f_T\cdot(-1)^{|(S\cup\{n+1\})\cap T|-1}\\ &=g_{0,S}+g_{1,S} \end{aligned}$$

同理，右部的表达式：

$$\begin{aligned} f'_{1,S\cup\{n-1\}}&=\sum_{0\le T<2^n}f_T\cdot(-1)^{|(S\cup\{n+1\})\cap T|}\\ &=\sum_{0\le T<2^{n-1}}f_T\cdot(-1)^{|S\cap T|}+\sum_{2^{n-1}\le T<2^n}f_T\cdot(-1)^{|(S\cup\{n+1\})\cap T|}\\ &=g_{0,S}-g_{1,S} \end{aligned}$$

逆变换记得每层 $\div2$。

void Xor(int n, LL* f, bool rev) {  // 0: 正变换，1: 逆变换
    for (int l = 2; l <= (1 << n); l *= 2)
        for (int i = 0; i < (1 << n); i += l)
            for (int k = 0; k < l / 2; k++) {
                LL u = f[i + k], v = f[i + k + l / 2];
                f[i + k] = u + v, f[i + k + l / 2] = u - v + mod;
                if (f[i + k] >= mod) f[i + k] -= mod;
                if (f[i + k + l / 2] >= mod) f[i + k + l / 2] -= mod;
                if (rev) (f[i + k] *= inv2) %= mod, (f[i + k + l / 2] *= inv2) %= mod;
            }
}