标签：rev frac int 多项式 全家 len pmod equiv

每次复习完下一次都会忘，这次下定决心一定要记下来！！！

FFT 和 NTT

板子，直接拿过来（包括了其他的定义）：

int n, m, rev[maxn];
int qpow(int x, int k, int p) {
	int res = 1;
	while(k) {
		if(k & 1)
			res = res * x % p;
		k >>= 1, x = x * x % p;
	}
	return res;
}
void prepare(int len) {
	for (int i = 0; i < len; i++) {
		rev[i] = rev[i >> 1] >> 1;
		if(i & 1)
			rev[i] |= len >> 1;
	}
}
struct Poly {
	vector<int> a;
	int size() {
		return a.size();
	}
	int& operator[](int x) {
		return a[x];
	}
	void resize(int N) {
		a.resize(N);
	}
	void NTT(int f) {
		for (int i = 1; i < a.size(); i++)
			if(i < rev[i])
				swap(a[rev[i]], a[i]);
		for (int h = 2; h <= a.size(); h <<= 1) {
			int d = qpow((f == 1 ? gb : gi), (mod - 1) / h, mod);
			for (int i = 0; i < a.size(); i += h) {
				int nw = 1;
				for (int j = i; j < i + h / 2; j++) {
					int a0 = a[j], a1 = a[j + h / 2] * nw % mod;
					a[j] = (a0 + a1) % mod, a[j + h / 2] = (a0 - a1 + mod) % mod;
					nw = nw * d % mod;
				}
			}
		}
		if(f == -1) {
			int inv = qpow(a.size(), mod - 2, mod);
			for (int i = 0; i < a.size(); i++)
				a[i] = a[i] * inv % mod;
		}
	}
	void read() {
		for (int i = 0; i < a.size(); i++)
			cin >> a[i];
	}
	void print() {
		for (int i = 0; i < a.size(); i++)
			cout << a[i] << " ";
		cout << endl;
	}
	friend Poly operator*(Poly f, Poly g) {
		int len = 1, t = f.size() + g.size() - 1;
		while(len < t)
			len <<= 1;
		prepare(len);
		f.resize(len), g.resize(len);
		f.NTT(1), g.NTT(1);
		for (int i = 0; i < len; i++)
			f[i] = f[i] * g[i] % mod;
		f.NTT(-1); f.resize(t);
		return f;
	}
}

多项式求逆

假设我们已经求出来了：

\[A\times B'\equiv 1 \pmod {x^{\lceil\frac{n}{2}\rceil}} \]

那么我们要求：

\[A\times B\equiv 1\pmod {x^{n}} \]

我们先做差，得到：

\[(B - B')\equiv 0\pmod {x^{\lceil\frac{n}{2}\rceil}} \]

然后平方，得到：

\[(B-B')^2\equiv 0\pmod {x^n} \]

\[B^2 - 2BB' + B'^2 \equiv 0\pmod {x^n} \]

左右同时乘 \(A\)，得到：

\[B-2B'+AB'^2\equiv 0\pmod {x^n} \]

\[B\equiv-AB'^2+2B' \pmod {x^n} \]

按这个柿子计算即可，注意没有必要把 NTT 出来的结果直接 NTT 回来，可以直接乘起来加起来。

Poly get_inv(Poly f, int lim) {
	if(lim == 1) {
		Poly ans; ans.resize(1);
		ans[0] = qpow(f[0], mod - 2, mod);
		return ans;
	}
	Poly ans = get_inv(f, lim + 1 >> 1);
	int len = 1;
	while(len < lim * 2)
		len <<= 1;
	prepare(len);
	f.resize(lim), f.resize(len), ans.resize(len);
	f.NTT(1), ans.NTT(1);
	for (int i = 0; i < len; i++)
		ans.a[i] = ans.a[i] * (2 - f.a[i] * ans.a[i] % mod + mod) % mod;
	ans.NTT(-1);
	ans.resize(lim);
	return ans;
}

注意，这里需要先 f.resize(lim)，因为我们需要排除多余的位。

多项式除法

我们记 \(F_R(x) = x^nF(\frac{1}{x})\)，那么就有：

\[F(x) = G(x)Q(x)+R(x) \]

\[F(\frac{1}{x})=G(\frac{1}{x})Q(\frac{1}{x})+R(\frac{1}{x}) \]

\[x^nF(\frac{1}{x}) = x^mG(\frac{1}{x})x^{n-m}Q(\frac{1}{x})+x^{n-m+1}\times x^{m-1}R(\frac{1}{x}) \]

\[\]

标签：rev,frac,int,多项式,全家,len,pmod,equiv
From： https://www.cnblogs.com/LUlululu1616/p/18473185