Fork me on GitHub

多项式学习笔记

开始跳楼了

多项式部分简介

定义简介

一个以$x$为变量的定义在代数域$F$上,将函数$A(x)$表示为:

其中我们称$a_0,a_1,\dots,a_{n-1}$为系数,如果一个多项式的最高次的非零系数为$a_k$,那么称$A(x)$的次数为$k$,记为$degree(A)=k$,任何一个大于该多项式次数的整数都是这个多项式的次数界.

多项式的表示

  1. 系数表达 :
    对一个次数界为$n$的多项式$A(x)=\sum_{j=0}^{n-1}a_jx^j$而言,其系数表达是一个由系数组成的向量$\text{a}=(a_0,a_1,\dots,a_{n-1})$.
    在给定系数求值时,采用霍纳法则(秦九邵算法)可以实现在$O(n)$的复杂度内完成求值运算.

    扩充:霍纳法则:

    1
    2
    3
    void Horner (){
    for(int i=n-1;i>=1;i--)
    ans*=x,ans+=a[i];
  2. 点值表达
    一个次数界为$n$的多项式$A(x)$的点值表达就是一个由$n$个点值对组成的集合

    使得对$k=0,1,\dots,n-1$,所有$x_k$各不相同

    则$A(x)=\sum_{j=0}^{n-1}A(x_j)$

多项式的乘法

这是多项式最核心的操作
即给定两个多项式$f(x)$和$g(x)$

要计算多项式$Q(x)=f(x).g(x):$

常规系数表达的计算是$O(n^2)$的,可以通过快速傅里叶变换在$O(nlogn)$下计算

多项式的逆元

对于多项式$f(x)$,若存在$g(x)$满足:

则称$g(x)$为$f(x)$在模$x^n$下的逆元,记作$f^{-1}(x)$

多项式的余数和商

对于多项式$f(x),g(x)$ ,存在唯一的$Q(x)$满足:

则称$Q(x)$为$f(x)$除$g(x)$的商,$R(x)$为$f(x)$除$g(x)$的余数.亦可记作

多项式的对数函数与指数函数

  1. 对数
    对于一个多项式 $f(x),$ 可以将其对数函数看作其与麦克劳林级数的复合:

    注意这里常数项必须为$1$,也就是说求对数的多项式必须满足 $A(x)=1+\sum_{i=1}^{\infty} a_{i} z^{i}$ 。

  2. 多项式exp
    其指数函数同样可以这样定义:

    看到这种 $e^{A(x)}$ 的指数形式显然非常不好处理, 于是采用等式两边同时 $\ln$ 的方式。设 $F(x)=e^{f(x)},$ 则有 $\ln F(x)-f(x) \equiv 0 \quad\left(\bmod x^{n}\right)$ 。构造函数
    $G(F(x))=\ln F(x)-f(x),$ 牛顿迭代即可。

  3. 多项式的$k$次幂

    注意这里的$k$可以是一个实数,对于$k$的整数部分显然可以直接用快速幂优化,而对于$k$的小数部分,我们可以运用$A^k(x)=e^{k ln A(x)}$进行求解.事实上当 $A(x)$的常数项不为$1$的时候我们是可以进行这样的运算的,可以直接把$C^{-1}$乘到前面去 $\left(C^{-1}\right.$ 为 $A(x)$ 的常数项的逆$)$,于是可以用 $A^{k}(x)=C^{k}\left(C^{-1} A\right)^{k}(x)=C^{k} e^{k \ln \left(C^{-1} A(x)\right)}$ 来进行求解。但是注意到如果仅仅是求In的
    话是不能乘上逆元的, 因为把 $\ln \left(C^{-1} A(x)\right)$ 拆开来之后变成了 $\ln C^{-1}+\ln A(x),$ 而
    $\ln C^{-1}$ 本身就是没有定义的。

多项式的对数一般求法

我们设$f(x)$是一个平静的多项式,我们要求$ln[f(x)]$
则我们设$g(x)=ln[f(x)]$,那么$g^{\prime}(x)=\frac{f^{\prime}(x)}{f(x)}$,$\ln g(x)=\int \frac{g^{\prime}(x)}{g(x)} \mathrm{d} x$

麦克劳林级数

  1. 基本介绍:
    对于一个给定的函数 $f(x),$ 如果能找到一个幂级数 $\sum_{n=0}^{\infty} a_{n} x^{n},$ 使 成立,则称$f(x)$可展开成$x$的幂级数。 把$x=0$代入式$(1)$及上述各式,得于是把它们代回式$(1)$,得通常称式$(2)$为$f(x)$的麦克劳林展开式或$f(x)$在$x=0$处的幂级数展开式。式$(2)$中等号右端的级数称为$f(x)$的麦克劳林级数或$f(x)$展开成$x$的幂级数。
    可见,当$a_n=\frac{1}{n!}f^{(n)}(0)$求得系数的幂级数在它的收敛域内的和函数就是$f(x)$
  2. 麦克劳林级数展开的条件及方法

    定理$1$:
    设函数$f(x)$的麦克劳林级数的收敛半径$R>0$,当$n→∞$时,如果函数$f(x)$在任一固定点$x$处的$n$阶导数$f^{(n)}(x)$有界,则函数$f(x)$在收敛区间$(-R,R)$内能展开成麦克劳林级数.即

    把函数$f(x)$展开成幂级数,有直接展开法和间接展开法

    直接展开法

    利用麦克劳林级数公式将函数$f(x)$展开成$x$的幂级数的方法,称为直接展开法。步骤可归纳为:

    1. 求出 $f(x)$ 的各阶导数 $f^{\prime}(x), f^{\prime \prime}(x), \ldots, f^{(n)}(x), \ldots,$ 令 $x=0$ 得 $f(0), f^{\prime}(0), f^{\prime \prime}(0), \ldots, f^{(n)}(0), \ldots$
    2. 写出$f(x)$的麦克劳林级数并求出收敛半径$R$

    间接展开法

    利用麦克劳林级数展开函数,需要求高阶导数,比较麻烦,如果能利用已知函数的展开式,根据幂级数在收敛域内的性质,将所给的函数展开成幂级数,这种方法称为间接展开法

多项式的多点求值和插值

多项式的多点求值 $(Multi-point evaluation)$ 即给出一个多项式 $f(x)$ 和 $n$ 个点 $x_{1}, x_{2}, \ldots, x_{n}$ 求

多项式的插值 $(Interpolation)$ 即给出 $n+1$ 个点

求一个 $n$ 次多项式 $f(x)$ 使得这 $n+1$ 个点都在 $f(x)$ 上。
这两种操作的实质就是将多项式在 系数表示 和 点值表示间转化。

拉格朗日插值

这里是题目传送门

题目大意

给出$n$个点$P(x_i,y_i)$,将过这$n$个点的最多$n-1$次多项式记为$f(x)$,求$f(k)$的值.

方法1:牛顿插值法

  1. 差商的定义:
    函数$f(x)$在两个互异点$x_i,x_j$处的一阶差商定义为:

    二阶差商:

$k+1$阶差商:

  1. 差商的性质

    (参考连接)

    1. $k$阶差商可以表示为函数值$f(x_0),f(x_1),\dots,f(x_k)$的线性组合,即 差商具有对称性,即差商与节点的排列顺序无关.
    2. 若函数$f(x)$在包含节点区间$[a,b]$上存在$k$ 阶导数,则$k$阶差商与导数的关系为

      即$k$次多项式的$k$阶差商为常数,低于$k$次多项式的差商为$0$(推了一会柿子之后发现对于多项式$A(x)=a_0+a_1x^1+\dots+a_kx^k$,他的$k$阶差商就是$a_k$)

  2. 牛顿插值多项式

    1. 牛顿插值多项式的推导 然后我们由$a,b,c,d$柿子可以得到 我们从上到下把柿子分别标为$(1),(2),\dots,(n)$柿,然后我们发现 然后我们把这个大柿子的上边的部分称为牛顿插值公式$N_n(x)$,下边的部分称为插值余项$R_n(x)$(懒得写latex了直接扔图了)
      1e37ef766fec2a86f6d42d8cffd06ff4
    2. 求值
      说了这么多,我们来考虑怎么使用这个玩意求多项式的插值.我们发现,对于给定的$n$个点,我们可以在$O(n^2)$的复杂度内递推出他们的差商.而对于求值来说,我们发现也可以在$O(n^2)$的时间复杂度内求出.即首先要递推出$(x-x_0)\times(x-x_1)\times \dots \times (x-x_n)$然后再用我们之前预处理的差商相乘再求和即可.
    3. 代码
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      #include <iostream>
      #include <cstdlib>
      #define int long long
      #define HA 998244353

      using namespace std;

      int count , num;
      int dataX[2005];
      int lovivd[2005][2005];

      int ksm ( int x , int y ) {
      long long tmp = 1;
      while ( y ) {
      if ( y & 1 )
      tmp = 1ll * tmp * x % HA;
      x = 1ll * x * x % HA;
      y >>= 1;
      }
      return tmp % HA;
      }
      void init(){
      double x , y;
      cin >> count >> num;
      for ( int i = 0 ; i < count ; i++ ) {
      cin >> x >> y;
      dataX[i] = x;
      lovivd[i][0] = y;
      }
      return;
      }
      void pre () {
      int dis = 1;
      for ( int i = 0 ; i < count ; i++ ) {
      for ( int j = i ; j < count ; j++ ) {
      int tmp = ( ( lovivd[j + 1][i] - lovivd[j][i] ) * ksm ( dataX[j+1] - dataX[j + 1 - dis] , HA - 2 ) )%HA;
      lovivd[j + 1][i + 1] = tmp;
      }
      dis += 1;
      }
      return;
      }

      int work() {
      long long calcValue = 0,temp = 1;
      for ( int i = 0 ; i < count ; i++ ) {
      temp = 1;
      for ( int j = 0 ; j < i ; j++ )
      //计算(X-X0)*(X-X1).....*(X-Xn-1)
      temp = 1ll * temp * ( num - dataX[j] + HA ) % HA;
      //计算f(X0,X1,....,Xn)*(X-X0)*(X-X1).....*(X-Xn-1)
      temp = 1ll * temp % HA * lovivd[i][i] % HA;
      //计算f(X0,X1,....,Xn)*(X-X0)*(X-X1).....*(X-Xn-1)的和
      calcValue = ( calcValue + temp + HA ) % HA;
      }
      return calcValue;
      }

      signed main(){
      init();
      pre();
      cout << work () <<endl;
      return 0;
      }

方法2:待定系数法

设$f(x)=\sum_{i=0}^{n-1}a_ix_i$将每个$x_i$带入$f(x)$,有$f(x_i)=y_i$,然后就可以使用高斯消元解方程组了.
(高消会补的啊真的会补的啊别催了QAQ)

方法3:拉格朗日插值

基本求值

拉格朗日插值有一个好就是代码比牛顿插值好写(
我们把原来的点集$P$中的每一个点在$x$轴上的映射$(x_i,0)$记为$H_i$.对于每一个$i$,我们都选择$n$个点组成的点集{$P_i$} $\cup$ {$H_j |1\leq i \leq n,j\not= i$},然后做一条过这个$n$个点的至多$n-1$次的曲线$g_i(x)$.如图所示,$g_i$用彩色线,而原来的$f(x)$用黑色线表示(从$OI-wiki$上偷的图)

qaq

这样我们不难发现,对于某个$g_i(x)$,他们都过点$(x_i,y_i)$,并且其余点的函数值均为$0$,所以我们对于每个$g_i$可以构造出他们的表达式

又因为对于每一个$i$,都只有一条$g_i$经过点$P_i$,其余的点都经过$H_i$,所以这些$g_i$相加之后发现可以恰好等于$f(x)$,所以$f(x)$的表达式即为:

如果我们要求$f(k)$的值的话,那我们只需要直接将$k$带入进$x$即可,即

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<algorithm>
#include<cstdio>
#include<cstring>
const int maxn = 2010;
using ll = long long;
ll mod = 998244353;
ll n, k, x[maxn], y[maxn], ans, s1, s2;
ll powmod(ll a, ll x) {
ll ret = 1ll, nww = a;
while (x) {
if (x & 1)
ret = ret * nww % mod;
nww = nww * nww % mod;
x >>= 1;
}
return ret;
}
ll inv(ll x) {
return powmod(x, mod - 2);
}
int main() {
scanf("%lld%lld", &n, &k);
for (int i = 1; i <= n; i++)
scanf("%lld%lld", x + i, y + i);
for (int i = 1; i <= n; i++) {
s1 = y[i] % mod;
s2 = 1ll;
for (int j = 1; j <= n; j++)
if (i != j)
s1 = s1 * (k - x[j]) % mod, s2 = s2 * ((x[i] - x[j] % mod) % mod) % mod;
ans += s1 * inv(s2) % mod;
ans = (ans + mod) % mod;
}
printf("%lld\n", ans);
return 0;
}

求系数

不会生成函数,先咕咕咕了(

快速傅里叶变换(FFT)

概述

离散傅里叶变换(Discrete Fourier Transform,缩写为 DFT),是傅里叶变换在时域和频域上都呈离散的形式,将信号的时域采样变换为其 DTFT 的频域采样。

FFT 是一种高效实现 DFT 的算法,称为快速傅立叶变换(Fast Fourier Transform,FFT)。它对傅里叶变换的理论并没有新的发现,但是对于在计算机系统或者说数字系统中应用离散傅立叶变换,可以说是进了一大步。快速数论变换 (NTT) 是快速傅里叶变换(FFT)在数论基础上的实现。

在 1965 年,Cooley 和 Tukey 发表了快速傅里叶变换算法。事实上 FFT 早在这之前就被发现过了,但是在当时现代计算机并未问世,人们没有意识到 FFT 的重要性。一些调查者认为 FFT 是由 Runge 和 König 在 1924 年发现的。但事实上高斯早在 1805 年就发明了这个算法,但一直没有发表。

通俗地说,多项式由系数表示法转为点值表示法的过程,就是 DFT 的过程。相对地,把一个多项式的点值表示法转化为系数表示法的过程,就是 IDFT。而 FFT 就是通过取某些特殊的 的点值来加速 DFT 和 IDFT 的过程。

DFT(离散傅里叶变换)

(默认从这里开始所有的$n$都为$2$的整数次幂)
首先我们对于任意系数表达的多项式转化为点值表达的话,可以随便取$n$个$x$带入计算.但是我们会发现,如果我们这样操作的话,那么时间复杂度就是$O(n^2)$的.
但是DFT就是要让我们知道,我们可以带入一组非常神奇的$x$,这样就不用完成全部的次方的运算了.

考虑什么数能简化求幂的操作,我们首先想到的就是$\pm 1$或者$\pm i$,但是我们在实际操作时只有这四个数当作$x$是完全不够用的.

但是我们在复数平面上考虑一个单位圆
发现圆上所有的点都可以经过若干次方的操作变成$1$
然后我们如果把这个圆给$k$等分了的话,我们从$(1,0)$点开始,把这个点标成$0$号点,一直标号到$k-1$号,然后我们记编号为$i$的点代表的复数值为$\omega_{n}^{i}$,然后由复数的运算法则可知

我们把$\omega_{n}^{1}$称为$n$次单位根,而且每一个单位根都可以求出,即

那么$\omega_n^1,\omega_n^2,\dots,\omega_n^{n-1}$就为我们要带入的$x_0,x_1,\dots,x_{n-1}$

单位根的一些性质

1.

2.

3.

FFT(快速傅里叶变换)

我们发现我们在搞了一系列花里胡哨的东西之后,把我们选取的$x$带入原来的柿子里计算求值还是$O(n^2)$的,所以我们考虑优化,这就有了$FFT$.

我们首先设一个多项式$A(x)$

那么我们按照下标的奇偶性分成两半,就有

然后我们再把右边的柿子里的$x$提出来,发现就得到了

然后我们吃惊的发现左右两个柿子除了系数不同之外,长的是差不多的,所以我们设

那么我们显然可以发现:

然后我们设$k<\frac{n}{2}$,把$\omega_{n}^{k}$作为$x$带入$A(x)$中,就能得到

那么对于$A(\omega_n^{k+\frac{n}{2}})$的话我们带入,则有:

我们发现,只要知道了$A_1(\omega_{\frac{n}{2}}^k)$和$A_2(\omega_{\frac{n}{2}}^{k})$的值,那么我们就能快速的求出$A(\omega_n^k)$和$A(\omega_n^{k+\frac{n}{2}})$的值了.

所以对于某一段序列$\{A(\omega_n^1),A(\omega_n^2),\dots,A(\omega_n^n)\}$,我们只要扫描它的前半部分,那么我们就能求出整个序列的值.这样的话我们就可以分治来求了. 时间复杂度为$T(n)=2T(\frac{n}{2})+O(n)=O
(nlog_2n)$

IDFT离散傅里叶反变换

使用快速傅里叶变换将多项式的点值表达转化为系数表达,这个过程叫做离散傅里叶反变换.

我们先设$(d_0,d_1,\dots,d_{n-1})$为$(a_0,a_1,\dots,a_{n-1})$进行$DFT$后的结果.
这时候我们构造一个多项式$F(x)=d_0+d_1x+\dots+d_{n-1}x^{n-1}$.然后我们再设向量$(c_0,c_1,\dots,c_{n-1})$为原多项式进行$DFT$后的点值表示.其中$c_k$表示$F(x)$在$x=\omega_n^{-k}$的点值表示.

即$c_k=\sum_{i=0}^{n-1}d_i(\omega_n^{-k})^i$

然后我们考虑把$d_i$分解,用$a_i$表示,我们得到了

然后我们把$a_j$扔到外面,就得到了

然后我们把$(\omega_n^{-k})^i$转换为$(\omega_n^i)^{-k}$并把最后两项合并之后有

然后我们把$\sum_{i=0}^{n-1}(\omega_n^i)^{j-k}$单独拿出来,并且设$\xi=j-k$,然后我们发现这个柿子就等于

我们观察一下这个柿子,发现我们可以用等比数列求和公式来直接求出这个柿子的值,而且这个柿子恰好等于$0$.

那么原来的柿子就可以这样乱搞:

对于多项式 $A(x)$ 由插值节点 $\left(\omega_{n}^{0}, \omega_{n}^{1}, \omega_{n}^{2}, \ldots, \omega_{n}^{n-1}\right)$ 做离散傅里叶变换得到的点值向量
$\left(d_{0}, d_{1}, \ldots, d_{n-1}\right)$ 。我们将 $\left(\omega_{n}^{0}, \omega_{n}^{-1}, \omega_{n}^{-2}, \ldots, \omega_{n}^{-(n-1)}\right)$ 作为插值节点,
$\left(d_{0}, d_{1}, \ldots, d_{n-1}\right)$ 作为系数向量, 做一次离散傅里叶变换得到的向量每一项都除以 $n$ 之后得 到的 $\left(\frac{c_{0}}{n}, \frac{c_{1}}{n}, \ldots, \frac{c_{n-1}}{n}\right)$ 就是多项式的系数向量 $\left(a_{0}, a_{1}, \ldots, a_{n-1}\right)$ 。

注意到 $\omega_{n}^{-k}$ 是 $\omega_{n}^{k}$ 的共轭复数。

FFT朴素版代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>

inline int read () {
int s = 0 , w = 1;
char ch = getchar ();
while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}
while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}
return s * w;
}

using namespace std;
const int N = 1e6 + 10;
const double Pi = acos(-1.0);

int n , m;
struct CP {
double x, y;
CP ( double xx = 0 , double yy = 0 ) {
x = xx;
y = yy;
};
CP operator + ( const CP &tmp ) const {
return CP ( x + tmp.x , y + tmp.y );
};
CP operator - ( const CP &tmp ) const {
return CP ( x - tmp.x , y - tmp.y );
};
CP operator * ( const CP &tmp ) const {
return CP ( x * tmp.x - y * tmp.y , x * tmp.y + y * tmp.x );
};
bool operator == ( const CP &tmp ) const {
if ( x == tmp.x && y == tmp.y )
return true;
else return false;
}
} a[N], b[N];

void FFT ( CP *aa , int bord , int type ) {
if ( bord == 1 )
return;
CP a1[bord >> 1] , a2[bord >> 1];
for ( int i = 0 ; i <= bord ; i += 2 ) {
a1[i >> 1] = aa[i];
a2[i >> 1] = aa[i + 1];
}
FFT ( a1 , bord >> 1 , type );
FFT ( a2 , bord >> 1 , type );
CP W = CP ( cos ( 2.0 * Pi / bord ) , type * sin ( 2.0 * Pi / bord ) );
CP wn = CP ( 1 , 0 );
for ( int i = 0 ; i < ( bord >> 1 ) ; i++ ) {
aa[i] = a1[i] + wn * a2[i];
aa[i + ( bord >> 1)] = a1[i] - wn * a2[i];
wn = wn * W;
}
return;
}
int main () {
n = read () , m = read ();
for ( int i = 0 ; i <= n ; i++ )
a[i].x = read ();
for ( int i = 0 ; i <= m ; i++ )
b[i].x = read ();
int bord;
for ( bord = 1 ; bord <= n + m ; bord *= 2 );
FFT ( a , bord , 1 );
FFT ( b , bord , 1 );
for (int i = 0; i <= bord; i++)
a[i] = a[i] * b[i];
FFT ( a , bord , -1 );
for (int i = 0; i <= n + m ; i++)
printf("%d ", (int)( a[i].x / bord + 0.5 ) );
return 0;
}

迭代实现

先盗一下图(
diedai

我们观察一下原序列和后序列,然后我们发现了一个显然的的结论:
我们需要求的序列实际是原序列下标的二进制反转!

因此我们对序列按照下标的奇偶性分类的过程其实是没有必要的,所以这样我们可以$O(n)$的利用某种操作得到我们要求的序列,然后不断向上合并就好了

FFT代码(迭代实现)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>

inline int read () {
int s = 0 , w = 1;
char ch = getchar ();
while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}
while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}
return s * w;
}

using namespace std;
const int N = 4e6 + 10;
const double Pi = acos(-1.0);

int n , m;
struct CP {
double x, y;
CP ( double xx = 0 , double yy = 0 ) {
x = xx;
y = yy;
};
CP operator + ( const CP &tmp ) const {
return CP ( x + tmp.x , y + tmp.y );
};
CP operator - ( const CP &tmp ) const {
return CP ( x - tmp.x , y - tmp.y );
};
CP operator * ( const CP &tmp ) const {
return CP ( x * tmp.x - y * tmp.y , x * tmp.y + y * tmp.x );
};
bool operator == ( const CP &tmp ) const {
if ( x == tmp.x && y == tmp.y )
return true;
else return false;
}
} a[N], b[N];

int bord , l , r[N];

void FFT ( CP *A , int type ) {
for ( int i = 0 ; i < bord ; i++ )
if ( i < r[i] ) //r[i]是预处理出的i应该在的位置
swap ( A[i] , A[r[i]] );
for ( int mid = 1 ; mid < bord ; mid <<= 1 ) {
CP Wn ( cos ( Pi / mid ) , type * sin ( Pi / mid ) );
for ( int R = mid << 1 , j = 0 ; j < bord ; j += R ) {
CP w ( 1 , 0 );
for ( int k = 0 ; k < mid ; k++ ) {
CP x = A[j + k] , y = w * A[j + mid + k];
A[j + k] = x + y;
A[j + mid + k] = x - y;//蝴蝶变换
w = w * Wn;
}
}
}
}
int main () {
n = read () , m = read ();
for ( int i = 0 ; i <= n ; i++ )
a[i].x = read ();
for ( int i = 0 ; i <= m ; i++ )
b[i].x = read ();
for ( bord = 1 ; bord <= n + m ; bord *= 2 , l++ );
for ( int i = 0 ; i <= bord ; i++ )
r[i] = ( r[i >> 1] >> 1 ) | ( ( i & 1 ) << ( l - 1 ) );
FFT ( a , 1 );
FFT ( b , 1 );
for (int i = 0; i <= bord; i++)
a[i] = a[i] * b[i];
FFT ( a , -1 );
for (int i = 0; i <= n + m ; i++)
printf("%d ", (int)( a[i].x / bord + 0.5 ) );
return 0;
}

快速数论变换(NTT)

因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:多项式学习笔记

文章作者:兮水XiShui丶

发布时间:2020年11月02日 - 16:11

最后更新:2020年11月16日 - 17:11

原始链接:http://krrrr.top/2020/11/02/多项式学习笔记/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。