多项式的简单四则运算

有加减乘除

加减比较native

---

多项式乘法

FFT：在\(O(nlogn)\)的时间内实现多项式的系数表示形式与点值表示形式的转换，作用域：实数

NTT：在\(O(nlogn)\)的时间内实现多项式的系数表示形式与点值表示形式的转换，作用域：有原根的模

MTT:

---

\[考虑一个n次多项式F(x) = \sum_{i = 1}^nx^ia_i\\ 考虑怎么快速求出其n个不重合的点的点值\\ \]

在实数域上FFT：

有一个玩意叫做n次单位根\(W_n^i\)

考虑把这个玩意带入进去,观察一下整个式子

\[不妨考虑n为二次整数次幂\\ F(x) = \sum_{i = 0}^{n - 1} x^ia_i = (x^0a_0 + ...+x^{n - 1}a_{n - 1})\\ = x^0a_0 + x^2_2 + ...+x^{n - 2}a_{n - 2} + x (x^0a_1 + x^2a_3+...+x^{n - 1}a_{n - 1})\\ F_1(x) = a_0 + a_2x^1 + ... +a_{n - 2}x^{\frac{n}{2} - 1}\\ F_2(x) = a_1 + a_3x^1 + ... +a_{n - 1}x^{\frac{n}{2} - 1}\\ F(x) = F_1(x^2) + xF_2(x^2)\\ 将一个单位根w_n^k带进去\\ F(w_n^k) = F_1(w_n^{2k}) + w_n^kF_2(w^{2k}_n)\\ 又因为单位根有一个性质:w_{2n}^{2k} = w^k_n\\ k < \frac{n}{2}\\ 有F(w_n^k) = F_1(w_{\frac{n}{2}}^{k}) + w_n^kF_2(w^{k}_{\frac{n}{2}})\\ F(w_n^{k + \frac{n}{2}}) = F_1(w_{\frac{n}{2}}^{k}) - w_n^kF_2(w^{k}_{\frac{n}{2}})\\ 发现每一次把问题分成了一半，统计是O(n)的\\ 故总的复杂度为O(nlogn)\\ \]

考虑如何将点值表达式转换为系数表示

考虑单位根的奇妙性质:

\[w_n^{k + \frac{n}{2}} = -w_n^k \]

考虑将n次单位根的倒数带进去得到的点值表达式

\[F(w_n^{0}) , F(w_n^{-1}),F(w_n^{-2})...,F(w_n^{-{n - 1}})\\ G(w_n^{-k}) = \sum_{i = 0}^{n - 1}F(w_n^i)w_n^{-ik}\\ =\sum_{i = 0}^{n - 1} (\sum_{j = 0}^{n - 1}a_jw_n^{ij}) w_n^{-ik}\\ = \sum_{j = 0}^{n - 1}a_j\sum_{i = 0}^{n - 1}w_n^iw_n^{(j - k)}\\ 发现后面这个式子实际上是一个等比数列求和\\ 于是可以推导得 后面这个式子只有\\ j = k : n\\ j != k : 0\\ 有\sum_{j = 0}^{n - 1}a_j\sum_{i = 0}^{n - 1}w_n^iw_n^{(j - k)}\\ =n*a_k\\ 故a_k = \frac{G(w_n^k)}{n} \]

---

回到FFT

上面的递归，每次都要按奇偶划分系数，实际上常数是非常的的

考虑更简便的方法：

不妨考虑整个系数序列递归到叶子的情况

发现叶子的系数分布，是0到\(n - 1\)的二进制倒置后的值

\[000,001,010,011,100,101,110,111\\ ->\\ 000,100,010,110,001,101,011,111\\ \]

于是可以\(O(n)\)递推

\[f[i] = f[i >> 1] + (i \& 1) << (log_2n - 1) \]

然后在FFT里面以 长度，起点做就好了

代码实现如下

#include<bits/stdc++.h>
#define MAXN 2000005
typedef double ll;
const ll PI = acos(-1.0);
using namespace std;

int n,m;
int lim,len;
int res[MAXN];

struct node{ll dx,dy;}a[MAXN],b[MAXN],c[MAXN];
node operator + (node A , node B){return (node){A.dx + B.dx , A.dy + B.dy};}
node operator - (node A , node B){return (node){A.dx - B.dx , A.dy - B.dy};}
node operator * (node A , node B){return (node){A.dx * B.dx - A.dy * B.dy , A.dx * B.dy + A.dy * B.dx};}

node wn(double sz , int tp){
	ll zz = 2.0 * PI / sz;
	if(tp == (-1))return (node){cos(zz) , -sin(zz)};
	return (node){cos(zz) , sin(zz)};
}

void fft(node f[] , int tp){
	for(int i = 0 ; i < len ; i++)if(i < res[i])swap(f[i] , f[res[i]]);
	for(int k = 1 ; k < len ; k = k + k){
		node w1 = wn(k << 1 , tp) , w , A , B;
		for(int i = 0 ; i < len ; i = i + k + k){
			w = (node){1 , 0};
			for(int j = 0 ; j < k ; j++ , w = w * w1){
				A = f[i + j] , B = f[i + j + k] * w;
				f[i + j] = A + B;
				f[i + j + k] = A - B;
			}	
		}
	}
	if(tp == (-1))for(int i = 0 ; i < len ; i++)f[i].dx /= (len * 1.0);
	
}

int main(){
	scanf("%d%d" , &n , &m);
	for(int i = 0 ; i <= n ; i++)scanf("%lf" , &a[i].dx);
	for(int i = 0 ; i <= m ; i++)scanf("%lf" , &b[i].dx);
	len = 1 , lim = 0;
	while(len <= (n + m + 2))len = len + len , lim++;
	for(int i = 1 ; i < len ; i++){
		res[i] = (res[i >> 1] >> 1) | ((i & 1) << (lim - 1));
	}
	fft(a , 1);
	fft(b , 1);
	for(int i = 0 ; i < len ; i++)c[i] = a[i] * b[i];
	fft(c , -1);
	for(int i = 0 ; i < n + m + 1 ; i++)printf("%d " , (int)(c[i].dx + 0.5));
	
}

---

考虑在模意义下怎么做

考虑998244353的原根，有一个为3

经过一些数学推导，发现原根在模意义下与单位根的性质相似

有\(w_n = g^{\frac{p - 1}{n}}\ mod p\)

其余的与单位根相似，不明白为什么之前写的常数这么大

代码如下：

#include<bits/stdc++.h>
#define MAXN 5000005
typedef long long ll;
const ll mod = 998244353;
const ll g = 3;
using namespace std;

int n,m,limit,len;
ll a[MAXN],b[MAXN],c[MAXN];
int res[MAXN];

int poww(ll x , int y){
	ll zz = 1;
	while(y){
		if(y & 1)zz = 1ll * x * zz % mod;
		x = (1ll * x * x) % mod;
		y = y >> 1;
	}
	return zz;
}

//wn = 

void NTT(ll f[] , int tp){
	for(int i = 0 ; i < len ; i++)if(i < res[i])swap(f[i] , f[res[i]]);
	for(int k = 1 ; k < len ; k = k + k){
		ll w1 = poww(3 , (mod - 1) / (k << 1)) , w , A , B;
		if(tp == (-1))w1 = poww(w1 , mod - 2);
		for(int i = 0 ; i < len ; i = i + k + k){
			w = 1;
			for(int j = 0 ; j < k ; j++ , w = w * w1 % mod){
				A = f[i + j] , B = f[i + j + k] * w % mod;
				f[i + j] = ((A + B) % mod + mod) % mod;
				f[i + j + k] = ((A - B) % mod + mod) % mod;
			}	
		}
	}
	if(tp == 1)return;
	ll zz = poww(len , mod - 2);
	for(int i = 0 ; i < len ; i++)f[i] = (1ll * f[i] * zz) % mod;
	
}

int main(){
	scanf("%d%d" , &n , &m);
	for(int i = 0 ; i <= n ; i++)scanf("%lld" , &a[i]);
	for(int i = 0 ; i <= m ; i++)scanf("%lld" , &b[i]);
	len = 1 , limit = 0;
	while(len <= (n + m + 1))len = len + len , limit++;
	for(int i = 1 ; i < len ; i++)res[i] = (res[i >> 1] >> 1) | ((i & 1) << (limit - 1));
	NTT(a , 1);
	NTT(b , 1);
	for(int i = 0 ; i < len ; i++)c[i] = 1ll * a[i] * b[i] % mod;
	NTT(c , -1);
	for(int i = 0 ; i < n + m + 1 ; i++)printf("%lld " , c[i]);
	
	
}

---

P1919 【模板】A*B Problem 升级版（FFT 快速傅里叶变换）

板子题

#include<bits/stdc++.h>
#define MAXN 5000005
typedef long long ll;
const ll mod = 998244353;
const ll g = 3;
using namespace std;

int n,m,limit,len,res[MAXN];
ll a[MAXN],b[MAXN],c[MAXN];
int sz;
char s[MAXN];

ll poww(ll x , int y){
	ll zz = 1;
	while(y){
		if(y & 1)zz = zz * x % mod;
		x = x * x % mod;
		y = y >> 1;
	}
	return zz;
}

void NTT(ll f[] , int tp){
	for(int i = 0 ; i < len ; i++)if(i < res[i])swap(f[i] , f[res[i]]);
	for(int k = 1 ; k < len ; k = k + k){
		ll w1 = poww(3 , (mod - 1) / (k << 1)) , w , A , B;
		if(tp == (-1))w1 = poww(w1 , mod - 2);
		for(int i = 0 ; i < len ; i = i + k + k){
			w = 1;
			for(int j = 0 ; j < k ; j++ , w = w * w1 % mod){
				A = f[i + j] , B = f[i + j + k] * w % mod;
				f[i + j] = ((A + B) % mod + mod) % mod;
				f[i + j + k] = ((A - B) % mod + mod) % mod;
			}	
		}
	}
	if(tp == 1)return;
	ll zz = poww(len , mod - 2);
	for(int i = 0 ; i < len ; i++)f[i] = (1ll * f[i] * zz) % mod;
}

int main(){
	scanf("%s" , s) , sz = strlen(s) , n = sz - 1;
	for(int i = 0 ; i <= n ; i++)a[i] = s[n - i] - '0';
	scanf("%s" , s) , sz = strlen(s) , m = sz - 1;
	for(int i = 0 ; i <= m ; i++)b[i] = s[m - i] - '0';

	len = 1 , limit = 0;
	while(len <= (n + m + 4)){
		len = len + len , limit++;	
	}
	for(int i = 1 ; i < len ; i++)res[i] = (res[i >> 1] >> 1) | ((i & 1) << (limit - 1));
	
	NTT(a , 1);
	NTT(b , 1);
	for(int i = 0 ; i < len ; i++)c[i] = (a[i] * b[i] % mod + mod) % mod;
	NTT(c , -1);
	
	
	for(int i = 0 ; i < n + m + 1 ; i++){
		c[i + 1] = c[i + 1] + c[i] / 10 , c[i] %= 10;	
	}
	int len = n + m + 1;
	while(c[len] >= 10)c[len + 1] = c[len + 1] + c[len] / 10 , c[len] %= 10 , len++;
	while(c[len] == 0)len--;
	for(int i = len ; i >= 0 ; i--)cout<<c[i];

}

---

分治FFT

例题：lgP4721 【模板】分治 FFT

\[给定序列g_{1...n - 1},求序列f_{0...n - 1}\\ f_i = \sum_{j = 1}^if_{i - j}g_j , f_0 = 1\\ 对于模数998244353取模 \]

考虑cdq分治

递归区间为\([L,R] , mid = (L + R) / 2\)

考虑\([L , mid]\)对区间\([mid + 1 , R]\)的贡献

\[f_i += \sum_{j = l}^{mid}f_j * g_{i - j} \]

发现这就是一个很简单的卷积形式

直接类似于cdq分治的形式就好了

复杂度大概是\(O(nlog^2n)\)

代码如下：lgP4721

#include<bits/stdc++.h>
#define MAXN 500005
typedef long long ll;
const ll mod = 998244353;
using namespace std;

int n;
ll g[MAXN],ans[MAXN];
ll poww(ll x , int y){
	ll zz = 1;
	while(y){
		if(y & 1)zz = zz * x % mod;
		x = x * x % mod;
		y = y >> 1;
	}
	return zz;
}

int limit,len;
ll a[MAXN],b[MAXN],res[MAXN];

void NTT(ll f[] , int tp){
	for(int i = 1 ; i < len ; i++)res[i] = ((res[i >> 1] >> 1) | ((i & 1) << (limit - 1)));
	for(int i = 0 ; i < len ; i++)if(i < res[i])swap(f[i] , f[res[i]]);
		for(int k = 1 ; k < len ; k = k + k){
			ll w1 = poww(3 , (mod - 1) / (k << 1)) , w , A , B;
			if(tp == (-1))w1 = poww(w1 , mod - 2);
			for(int i = 0 ; i < len ; i = i + k + k){
				w = 1;
				for(int j = 0 ; j < k ; j++ , w = w * w1 % mod){
					A = f[i + j] , B = f[i + j + k] * w % mod;
					f[i + j] = ((A + B) % mod + mod) % mod;
					f[i + j + k] = ((A - B) % mod + mod) % mod;
				}	
			}
		}
	if(tp == 1)return;
	ll zz = poww(len , mod - 2);
	for(int i = 0 ; i < len ; i++)f[i] = (1ll * f[i] * zz) % mod;
}

void cdq(int l , int r){
	if(l == r)return;
	int mid = (l + r) >> 1;
	cdq(l , mid);
	for(int i = l ; i <= mid ; i++)a[i - l] = ans[i] , b[i - l] = g[i - l];
	for(int i = mid + 1 ; i <= r ; i++)a[i - l] = 0 , b[i - l] = g[i - l];
	len = 1 , limit = 0;
	while(len <= (r - l + 1))len = len + len , limit++;
	for(int i = r - l + 1 ; i <= len ; i++)a[i] = b[i] = 0;
	NTT(a , 1) , NTT(b , 1);
	for(int i = 0 ; i < len ; i++)a[i] = (a[i] * b[i] % mod + mod) % mod;
	NTT(a , -1);
	for(int i = mid + 1 ; i <= r ; i++)ans[i] = (ans[i] + a[i - l]) % mod;
	cdq(mid + 1 , r);
	
}

int main(){
	scanf("%d" , &n) , ans[0] = 1;
	for(int i = 1 ; i < n ; i++)scanf("%d" , &g[i]);
	len = 1;while(len < n)len = len + len;
	cdq(0 , len - 1);
	for(int i = 0 ; i < n ; i++)cout<<ans[i]<<" ";
}

也有多项式求逆的做法，之后补

---

任意模数多项式乘法(MTT)

这个东西一般处理任意模数，可以用于适当的加强题目

1.把答案在三个有原根的模数下求出来，然后对于每一个答案都做一次CRT，9次

2.分解每一个数成\(\sqrt{mod} * p + q = a_i\)的形式 , 然后做多项式乘法暴力乘

3.MTT（论文里面的玩意）

方法2实现

#include<bits/stdc++.h>
#define MAXN 400005
typedef long double ll;
typedef long long LL;
const ll PI = acos(-1.0);
using namespace std;

int n,m,limit,len;
int res[MAXN];
LL ans[MAXN],part = 32768,p;
struct node{ll dx,dy;}a1[MAXN],b1[MAXN],a2[MAXN],b2[MAXN],X[MAXN];

node operator + (node A , node B){return (node){A.dx + B.dx , A.dy + B.dy};}
node operator - (node A , node B){return (node){A.dx - B.dx , A.dy - B.dy};}
node operator * (node A , node B){return (node){A.dx * B.dx - A.dy * B.dy , A.dx * B.dy + A.dy * B.dx};}

node wn(ll sz , int tp){
	ll zz = 2.0 * PI / sz;
	if(tp == (-1))return (node){cos(zz) , -sin(zz)};
	return (node){cos(zz) , sin(zz)};
}

void fft(node f[] , int tp){
	for(int i = 0 ; i < len ; i++)if(i < res[i])swap(f[i] , f[res[i]]);
	for(int k = 1 ; k < len ; k = k + k){
		node w1 = wn(k << 1 , tp) , w , A , B;
		for(int i = 0 ; i < len ; i = i + k + k){
			w = (node){1 , 0};
			for(int j = 0 ; j < k ; j++ , w = w * w1){
				A = f[i + j] , B = f[i + j + k] * w;
				f[i + j] = A + B;
				f[i + j + k] = A - B;
			}	
		}
	}
}

void solve(node A[] , node B[] , LL res){
	for(int i = 0 ; i < len ; i++)X[i].dx = X[i].dy = 0;
	for(int i = 0 ; i < len ; i++)X[i] = A[i] * B[i];
	fft(X , -1);
    for(int i=0;i<=n+m;++i)(ans[i]+=(LL)(X[i].dx/len+0.5)%p*res%p)%=p;
}

void MTT(node f1[] , node f2[] , node g1[] , node g2[]){
	fft(f1 , 1) , fft(f2 , 1) , fft(g1 , 1) , fft(g2 , 1);
	solve(f1 , g1 , part * part);
	solve(f1 , g2 , part);
	solve(f2 , g1 , part);
	solve(f2 , g2 , 1);
	for(int i = 0 ; i <= n + m ; i++){
		cout<<(ans[i] % p + p) % p<<" ";
	}
}

int main(){
	scanf("%d%d%lld" , &n , &m , &p);LL zz;
	for(int i = 0 ; i <= n ; i++){
		scanf("%lld" , &zz);
		a1[i].dx = zz / part;
		a2[i].dx = zz % part;		
	}
	for(int i = 0 ; i <= m ; i++){
		scanf("%lld" , &zz);
		b1[i].dx = zz / part;
		b2[i].dx = zz % part;		
	}
	len = 1 , limit = 0;
	while(len <= (n + m + 2))len = len + len , limit++;
	for(int i = 1 ; i < len ; i++)res[i] = (res[i >> 1] >> 1) | ((i & 1) << (limit - 1));
	MTT(a1 , a2 , b1 , b2);
	
}

---

多项式乘法逆

给定你一个n次多项式\(F(x)\),让你求一个多项式\(G(x)\)满足\(F(x) * G(x) = 1\ (mod\ x^n)\)

具体而言，相当于找一个多项式函数关于乘法意义下的逆元

\[F(x)H(x) = 1\ (mod\ x^{\frac{n}{2}})\\ F(x)H(x) = 1\ (mod\ x^{\frac{n}{2}})\\ 有F(x)G(x) = 1 (mod\ x^{\frac{n}{2}})\\ 有F(x)(G(x) - H(x)) = 0 (mod\ x^{\frac{n}{2}})\\ 平方有G^2(x) + H^2(x) = 2H(x)G(x) (mod\ x^n)\\ 两边再同时乘上F(x)\\ G(x) = 2H(x) - H^2(x)F(x) (mod\ x^n)\\ \]

于是就可以递归的去构造了

#include<bits/stdc++.h>
#define MAXN 400005
typedef long long ll;
const ll mod = 998244353;
using namespace std;

int n,len,limit,res[MAXN];
ll a[MAXN],c[MAXN];
ll H[MAXN],G[MAXN];

ll poww(ll x , int y){
	ll zz = 1;
	while(y){
		if(y & 1)zz = zz * x % mod;
		x = x * x % mod;
		y = y >> 1;
	}
	return zz;
}

void NTT(ll f[] , int tp){
	for(int i = 1 ; i < len ; i++)res[i] = (res[i >> 1] >> 1) | ((i & 1) << (limit - 1));
	for(int i = 0 ; i < len ; i++)if(i < res[i])swap(f[i] , f[res[i]]);
	for(int k = 1 ; k < len ; k = k + k){
		ll w1 = poww(3 , (mod - 1) / (k << 1)) , w , A , B;
		if(tp == (-1))w1 = poww(w1 , mod - 2);
		for(int i = 0 ; i < len ; i = i + k + k){
			w = 1;
			for(int j = 0 ; j < k ; j++ , w = w * w1 % mod){
				A = f[i + j] , B = f[i + j + k] * w % mod;
				f[i + j] = ((A + B) % mod + mod) % mod;
				f[i + j + k] = ((A - B) % mod + mod) % mod;
			}	
		}
	}
	if(tp == 1)return;
	ll zz = poww(len , mod - 2);
	for(int i = 0 ; i < len ; i++)f[i] = (1ll * f[i] * zz) % mod;
}

void solve(int LEN , int L){
	if(LEN == 1)return (void)(G[0] = poww(a[0] , mod - 2)); 
	solve((LEN + 1) >> 1 , L - 1);
	swap(H , G);
	len = 1 , limit = 0;
	while(len < (LEN << 1))len = len << 1 , limit++;
	for(int i = 0 ; i < LEN ; i++)G[i] = c[i] = 0;
	for(int i = 0 ; i < LEN ; i++)c[i] = a[i];
	for(int i = LEN ; i < len ; i++)c[i] = 0;
	NTT(c , 1) , NTT(H , 1);
	for(int i = 0 ; i < len ; i++)G[i] = ((H[i] * ((2ll - H[i] * c[i]) % mod + mod) % mod) % mod + mod) % mod;
	NTT(G , -1);
	for(int i = LEN ; i < len ; i++)G[i] = 0;
}

int main(){
	scanf("%d" , &n);for(int i = 0 ; i < n ; i++)scanf("%lld" , &a[i]);
	solve(n , limit);
	for(int i = 0 ; i < n ; i++)cout<<G[i]<<" ";
}

---

多项式ln,exp

引入对多项式的微分求导运算就可以做了

多项式ln

\[G(x) = ln(A(x))\\ G'(x) = \frac{A'(x)}{A(X)}\\ G(x) = \int G'(x) = \int \frac{A'(x)}{A(X)}\\ 直接对右边这个玩意多项式求逆+求导+积分一下就好了 \]

#include<bits/stdc++.h>
#define MAXN 400005
typedef long long ll;
const ll mod = 998244353;
using namespace std;

int n,m,len,limit,res[MAXN];
ll a[MAXN],c[MAXN];
ll H[MAXN],G[MAXN];

ll poww(ll x , int y){
	ll zz = 1;
	while(y){
		if(y & 1)zz = zz * x % mod;
		x = x * x % mod;
		y = y >> 1;
	}
	return zz;
}

void NTT(ll f[] , int tp){
	for(int i = 1 ; i < len ; i++)res[i] = (res[i >> 1] >> 1) | ((i & 1) << (limit - 1));
	for(int i = 0 ; i < len ; i++)if(i < res[i])swap(f[i] , f[res[i]]);
	for(int k = 1 ; k < len ; k = k + k){
		ll w1 = poww(3 , (mod - 1) / (k << 1)) , w , A , B;
		if(tp == (-1))w1 = poww(w1 , mod - 2);
		for(int i = 0 ; i < len ; i = i + k + k){
			w = 1;
			for(int j = 0 ; j < k ; j++ , w = w * w1 % mod){
				A = f[i + j] , B = f[i + j + k] * w % mod;
				f[i + j] = ((A + B) % mod + mod) % mod;
				f[i + j + k] = ((A - B) % mod + mod) % mod;
			}	
		}
	}
	if(tp == 1)return;
	ll zz = poww(len , mod - 2);
	for(int i = 0 ; i < len ; i++)f[i] = (1ll * f[i] * zz) % mod;
}

void solve(int LEN){
	if(LEN == 1)return (void)(G[0] = poww(a[0] , mod - 2)); 
	solve((LEN + 1) >> 1);
	swap(H , G);
	len = 1 , limit = 0;
	while(len < (LEN << 1))len = len << 1 , limit++;
	for(int i = 0 ; i < LEN ; i++)G[i] = c[i] = 0;
	for(int i = 0 ; i < LEN ; i++)c[i] = a[i];
	for(int i = LEN ; i < len ; i++)c[i] = 0;
	NTT(c , 1) , NTT(H , 1);
	for(int i = 0 ; i < len ; i++)G[i] = ((H[i] * ((2ll - H[i] * c[i]) % mod + mod) % mod) % mod + mod) % mod;
	NTT(G , -1);
	for(int i = LEN ; i < len ; i++)G[i] = 0;
}

int main(){
	scanf("%d" , &n) , m = n - 1;for(int i = 0 ; i < n ; i++)scanf("%lld" , &a[i]);
	solve(n);memset(H , 0 , sizeof(H));
	for(int i = 1 ; i < n ; i++)H[i - 1] = ((a[i] * (1ll * i)) % mod + mod) % mod;
	len = 1 , limit = 0;
	while(len <= (n + m + 1))len = len + len , limit++;
	NTT(H , 1) , NTT(G , 1);
	for(int i = 0 ; i < len ; i++)H[i] = (H[i] * G[i] % mod + mod) % mod;
	NTT(H , -1);memset(G , 0 , sizeof(G));
	for(int i = 0 ; i < len ; i++){
		G[i + 1] = (H[i] * poww(i + 1 , mod - 2) % mod + mod) % mod;
	}
	for(int i = 0 ; i < n ; i++)cout<<G[i]<<" ";
	
}

---

牛顿迭代

实数域上的牛顿迭代

常用来逼近某一些函数的零点

\[求函数F(x)的零点\\ 先大致故一下零点在哪里\\ 在零点附近取一个点(x_0 , F(x_0))\\ 在该点做一条切线与x轴相切 k = F'(x_0)\\ 交点为x_1\\ 即y - F(x_0) = F'(x_0)(x - x_0)\\ \frac{0 - F(x_0)}{F'(x_0)} + x_0 = x_1 \]

按上述过程反复迭代即可

函数域上的牛顿迭代，虽然上下两个部分关系并不大，但思想是类似的

\[给定一个F(x),让你求一个多项式f\ .st F(f) = 0\\ 考虑倍增构造\\ F(f) = 0\ (mod\ x^n) , f_0 = f\ (mod\ x^n)\\ 考虑F(f)在f = f_0除的泰勒展开\\ F(f) = \sum_{k = 0}\frac{F^{k}(f - f_0)^k}{k!}\\ k >= 2时，(f - f_0) ^ k = 0\ (mod\ x^{2*n})显然\\ 则有 F(f) = 0 = F(f_0) + F'(f_0)(f - f_0) \ (mod\ x^{2n})\\ 则f = f_0 - \frac{F(f_0)}{F'(f_0)} \ (mod\ x^{2n})\\ 如此下去就可以得到f \]

注意，这里的f虽然是函数，但我们把它当成常数来处理

---

多项式求逆就是一个很好的例子

---

多项式exp

\[B(x) = e^{A(x)}\\ 两边取对数 ln(B(x)) = A(x) \\ ln(B(x)) - A(x) = 0\\ 构造函数F(f) = ln(f) - A(x) \\ 采用牛顿迭代得到这个f就好了\\ 即f = (1 + A(x) - ln(f_0))*f_0 \]

---

多项式开方

\[B(x) = \sqrt{A(x)}\\ B^2(x) = A(x)\\ B^2(x) - A(x) = 0\\ 构造函数F(f) = f^2 - A(x) = 0\\ 即f = \frac{f_0^2 + A(f_0)}{2f_0} 直接套用牛顿迭代就好了 \]

---

下降幂多项式乘法

\[A(x) = \sum_{i = 0}a_ix^{\underline{i}}这个个下降幂多项式的例子 \]

咕~~~~~