CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

====== 多项式求逆 ======

准备工作

<code cpp>

void calc_rev(int &n,int &lim,const int m) {
	n = 1,lim = 0;
	while(n < m) n <<= 1,lim++;
	for(int i = 1; i < n; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << lim - 1);
}

</code>

递归复杂度 $O(nlogn)$

<code cpp>

void Inv(const int *a,int *b,const int len) { //多项式求逆
	static int c[N];
	if(len == 1) {
		b[0] = qpow(a[0],mod - 2);
		return;
	}
	Inv(a,b,len + 1 >> 1);
	int n,lim;
	calc_rev(n,lim,len << 1);
	for(int i = 0; i < n; i++) c[i] = a[i];
	for(int i = len; i < n; i++) c[i] = 0;
	NTT(c,n,1),NTT(b,n,1);
	for(int i = 0; i < n; i++) b[i] = (2 - (ll)c[i] * b[i] % mod + mod) * b[i] % mod;
	NTT(b,n,-1);
	for(int i = len; i < n; i++) b[i] = 0;
}

</code>

检查的方法:随机一个多项式求逆两次看看是不是自己。

CVBB ACM Team

用户工具

站点工具

页面工具