Nemlit 的博客

Nemlit 的博客

By a konjac

多项式学习笔记

posted on 2019-10-07 20:52:04 | under 未分类 |

太菜了并不是很理解多项式,简单记录一下,缓慢更新吧……

有问题问快速航

$FFT$

首先我们要求的柿子长这样:

$$c(k) = \sum_{i+j = k}a(i)*b(j)$$

大概思路:先把两个多项式转成点值 $(DFT)$ ,再把两个多项式的点值乘在一起,把新的点值转成多项式 $(IDFT)$ 即可

$DFT:$

首先要了解复数的运算

$$(a + b*i) +(c+d*i) = (a+c)+(b+d)*i$$ $$(a + b*i) -(c+d*i) = (a-c)+(b-d)*i$$ $$(a + b*i) *(c+d*i) = (a*c - b*d)+(a*d+b*d)*i$$

随便说下单位圆/单位根: 现在我们要把圆平分成 $n$ 个,每一个的大小应该是 $cos(2 Π /n), sin(2Π / n)$

步入正题,具体操作长这样: $$F(x) = a_0*x^0+a_1*x^1+a_2*x^2+……+a_n*x^n$$ 设 $F1(x) = a_0*x^0+a_2*x^1+……+a_{n}*x^{\frac{n}{2}}$ , $F2(x) = a_1*x^0+a_3*x^2+……+a_{n - 1}*x^{\frac{n}{2}}$ $$F(x) = F1(x^2)+x*F2(x^2)$$

现在我们只需要知道 $F1(x), F2(x)$ 就可以知道 $F(x)$ 了,于是我们可以递归处理(所以我们需要保证多项式的项数为 $2^x$ )

把单位根带到上述式子里面去,我们有:

$$F(w_n^x) = F1(w_n^{2*x})+w_n^x*F2(w_n^{2*x})$$

现在我们需要单位根的第一条性质(带到单位圆上就知道了):

$$w_{2n}^{2x} = w_{n}^x$$

顺便介绍性质二(还是画画图就知道了):

$$w_{n}^{x+\frac{n}{2}} = -w_{n}^x$$

通过性质一,我们可以把柿子化成: $$F(w_n^x) = F1(w_{\frac{n}{2}}^{x})+w_n^x*F2(w_{\frac{n}{2}}^{x})$$

由于我们只知道 $F1(x), F2(x)$ 的 $0-\frac{n}{2}$ 的所有点值要求出 $F(x)$ 的 $0-n$ 的所有点值

分类讨论一下:

如果 $x<\frac{n}{2}$ ,直接用 $F1,F2$ 的值就行

如果 $x≥\frac{n}{2}$ ,不妨设 $x=x+\frac{n}{2}$

$$F(w_n^{x+\frac{n}{2}}) = F1((w_{n}^{x+\frac{n}{2}})^2)+w_n^{x+\frac{n}{2}}*F2((w_{n}^{{x+\frac{n}{2}}})^2)$$ 由于第二条性质 $$F(w_n^{x+\frac{n}{2}}) = F1((-w_{n}^x)^2)-w_n^{x}*F2((-w_{n}^{x})^2)$$ $$F(w_n^x) = F1(w_{\frac{n}{2}}^{x})-w_n^x*F2(w_{\frac{n}{2}}^{x})$$

发现只有一个符号的区别

$IDFT$

我们假设我们通过 $DFT$ 求出了点值为 $a_0, a_1……, a_n$ ,最后我们要求出的值为 $A_0, A_1……, A_n$

其实我们只要解一个这样的方程组:

$$A_0*(w_n^0)^0+A_1*(w_n^0)^1+A_2*(w_n^0)^2+……+A_n*(w_n^0)^2$$ $$A_0*(w_n^1)^0+A_1*(w_n^1)^1+A_2*(w_n^1)^2+……+A_n*(w_n^1)^2$$ $$……$$ $$A_0*(w_n^{n - 1})^0+A_1*(w_n^{n - 1})^1+A_2*(w_n^{n - 1})^2+……+A_n*(w_n^{n - 1})^2$$

这就是一个矩阵形式了

第一个矩阵是所有的 $(w_n^x)^k$ ,我们计为矩阵V,第二个矩阵为所有的 $A_x$ 计为A,第三个矩阵为所有的 $a_x$ 计为a

于是我们的柿子变成了 $A*V=a$

如果我们知道 $V^{-1}$ ,那么我们有 $a*V^{-1} = A$ ,a即为所求

现在考虑求逆:

我们需要介绍性质三: $\sum_{j = 0}^{n - 1}(w_n^k)^j=[k==0]*n$

证明其实不难,画画图就好了,我们要求的柿子为: $\sum_{j = 0}^{n - 1}(w_n^k)^j$

如果 $k =0$ ,那么原式 $=\sum_{j = 0}^{n - 1} = n$

如果 $k≠0$ ,记 $s=\sum_{j =0}^{n - 1}(w_n^k)^j$

$s*w_n^k = \sum_{j=1}^{n}(w_n^k)^j =s-1+(w_n^k)^n = s$

因为 $w_n^k≠0$ ,所以 $s=0$

我们令 $V^{-1}(i, j) = (w_n^{-i})^j$

所以 $(V*V^{-1})(i, j)=\sum_{k =0}^{n-1}(w_n^{-i})^k*(w_n^k)^j=\sum_{k = 0}^{n - 1}(w_n^{j -i})^k$

根据性质三,当 $i=j$ 时 $(V*V^{-1})(i, i)=n$ ,否则 $=0$ ,只需要把每一项 $/n$ 即可

然后我们有发现,只需要把 $A$ 看成新的系数,把所有的 $(w_n^j)^k$ 看成 $(w_n^{-j})^k$ ,那么就是一边新的 $DFT$ 了

所以唯一的差别就是单位根前面乘了一个 $-1$ 即可

$Code:$

struct node {
    D x, y;
}a[maxn], b[maxn];
il node operator + (node a, node b) {return (node){a.x + b.x, a.y + b.y};}
il node operator - (node a, node b) {return (node){a.x - b.x, a.y - b.y};}
il node operator * (node a, node b) {return (node){a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x};}
int n, m, lim;
il void FFT(node *x, int f, int len) {
    if(len == 1) return;
    node f1[len >> 1], f2[len >> 1];
    for(re int i = 0; i < len; i += 2) f1[i / 2] = x[i], f2[i / 2] = x[i + 1];
    FFT(f1, f, len >> 1), FFT(f2, f, len >> 1);
    node w = (node){1, 0}, base = (node){cos(2.0 * pi / len), f * sin(2.0 * pi / len)};
    for(re int i = 0; i < (len >> 1); ++ i, w = w * base) {
        x[i] = f1[i] + w * f2[i], x[i + (len >> 1)] = f1[i] - w * f2[i];
    }
}
int main() {
    n = read(), m = read();
    rep(i, 0, n) a[i].x = read();
    rep(i, 0, m) b[i].x = read();
    while((1 << lim) <= n + m) ++ lim;
    FFT(a, 1, (1 << lim)), FFT(b, 1, (1 << lim));
    rep(i, 0, (1 << lim)) a[i] = a[i] * b[i];
    FFT(a, -1, (1 << lim));
    rep(i, 0, n + m) printf("%d ", (int)(a[i].x / (1 << lim) + 0.5));
    return 0;
}

讲讲迭代版的 $FFT$

通过打表发现:一个数x再最后一次出现的位置 $r[i]$ 是可以通过公式算出来的: $r[i] = (r[i >> 1] >> 1)\ |\ ((i\ \&\ 1) << (lim - 1))$

然后我们在 $FFT$ 前面把x交换到对应位置,然后用类似上述方法一个个合并即可(我不是懒,是怕东西太多页面卡)

$Code:$

il void FFT(node *x, int f, int len) {
    rep(i, 0, len - 1) if(i < r[i]) swap(x[i], x[r[i]]);
    for(int mid = 1; mid < len; mid <<= 1) {
        node base = (node){cos(pi / mid), f * sin(pi / mid)};
        for(re int p = mid * 2, j = 0; j < len; j += p) {
            node w = (node){1, 0};
            for(re int k = 0; k < mid; ++ k, w = w * base) {
                node a = x[j + k], b = w * x[j + k + mid];
                x[j + k] = a + b, x[j + k + mid] = a - b;
            }
        }
    } 
}
rep(i, 0, (1 << lim)) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (lim - 1));

$NTT:$

大概就是你把原根看成单位根,然后跑 $FFT$ 即可(我不是懒,是怕东西太多页面卡)

$Code:$

#define mod 998244353
#define invG 332748118
#define G 3
#define maxn 10000006
int n, m, a[maxn], b[maxn], l, lim = 1, r[maxn];
il int qpow(int a, int b) {
    int r = 1;
    while(b) {
        if(b & 1) r = 1ll * r * a % mod;
        a = 1ll * a * a % mod, b >>= 1;
    }
    return r;
}
il void NTT(int *x, int f, int len) {
    rep(i, 0, len) if(i < r[i]) swap(x[i], x[r[i]]);
    for(re int mid = 1; mid < len; mid <<= 1) {
        int base = qpow((f == 1) ? G : invG, (mod - 1) / (mid << 1));
        for(re int p = mid * 2, j = 0; j < len; j += p) {
            for(re int k = 0, w = 1; k < mid; ++ k, w = 1ll * w * base % mod) {
                int a = x[j + k], b = 1ll * w * x[j + k + mid] % mod;
                x[j + k] = (a + b) % mod, x[j + k + mid] = (a - b + mod) % mod;
            }
        }
    }
}
signed main() {
    n = read(), m = read();
    rep(i, 0, n) a[i] = read();
    rep(i, 0, m) b[i] = read();
    while(lim <= (n + m)) ++ l, lim <<= 1;
    rep(i, 0, lim) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    NTT(a, 1, lim), NTT(b, 1, lim);
    rep(i, 0, lim) a[i] = 1ll * a[i] * b[i] % mod;
    NTT(a, -1, lim);
    int inv = qpow(lim, mod - 2);
    rep(i, 0, n + m) printf("%d ", (1ll * a[i] * inv) % mod);
    return 0;
}

牛顿迭代

不会

泰勒展开

不会

任意模数 $NTT$

不会

多项式求逆

不会

分治 $FFT$

不会

多项式除法

不会

多项式开根

不会

多项式 $exp$

不会

多项式 $ln$

不会

生成函数

不会