Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

多项式

Posted on Edited on

大佬前辈在线讲课，无奈完全听不懂啊（QWQ）

  • 先写点自己的多项式没家桶。

多项式乘法luoguP3803 【模板】多项式乘法（FFT）

  • $NTT / FFT$ 均可。
  • $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
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 5e6 + 5;
const double Pi = acos(-1);
int n, m;
struct Node{
	double x, y;
	Node operator+(const Node & t) const 
	{
		return {x + t.x, y + t.y};
	}
	Node operator-(const Node & t) const 
	{
		return {x - t.x, y - t.y};
	}
	Node operator*(const Node & t) const 
	{
		return {x * t.x - y * t.y, x * t.y + y * t.x};
	}
}a[N], b[N];
int rev[N], bit, tot;
void fft(Node a[], int inv)
{
	for(int i = 0;i < tot;i ++)
	{
		if(i < rev[i]) swap(a[i], a[rev[i]]);
	}
	for(int mid = 1;mid < tot;mid <<= 1)
	{
		Node w1 = Node({cos(Pi / mid), inv * sin(Pi / mid)});
		for(int i = 0;i < tot;i += mid * 2)
		{
			Node wk = Node({1, 0});
			for(int j = 0;j < mid;j ++, wk = wk * w1)
			{
				Node x = a[i + j], y = wk * a[i + j + mid];
				a[i + j] = x + y, a[i + j + mid] = x - y;
			}
		} 
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 0;i <= n;i ++) scanf("%lf", &a[i].x);
	for(int i = 0;i <= m;i ++) scanf("%lf", &b[i].x);
	while((1 << bit) < n + m + 1) bit ++;
	tot = 1 << bit;
	for(int i = 0;i < tot;i ++)
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
	fft(a, 1), fft(b, 1);
	for(int i = 0;i <= tot;i ++) a[i] = a[i] * b[i];
	fft(a, -1);
	for(int i = 0;i <= n + m;i ++)
	{
		printf("%d ", (int)(a[i].x / tot + 0.5));
	}
	return 0;
}
  • $NTT$
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
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 3e6 + 5, mod = 998244353;
int r[N], bit, tot;
int a[N], b[N];
LL qpow(LL x, LL k)
{
	LL res = 1;
	while(k)
	{
		if(k & 1) res = res * x % mod;
		x = (x * x) % mod;
		k >>= 1;
	}
	return res;
}
void NTT(int x[], int op)
{
	for(int i = 0;i < tot; i ++)
		if(i < r[i]) swap(x[i], x[r[i]]);
	int mid, len, gn, g, a, b;
	for(mid = 1; mid < tot; mid <<= 1)
	{
		len = mid << 1;
		gn = qpow(3, (mod - 1) / len);
		if(op == -1) gn = qpow(gn, mod - 2);
		for(int i = 0;i < tot;i += len)
		{
			g = 1;
			for(int j = 0;j < mid;j ++, g = (LL) g * gn % mod)
			{
				a = x[i + j], b = (LL)g * x[i + j + mid] % mod;
				x[i + j] = (a + b) % mod;
				x[i + j + mid] = (a - b + mod) % mod;
			}
		}
	}
}
int n, m;
int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 0;i <= n;i ++) scanf("%d", &a[i]), a[i] = (a[i] + mod) % mod;
	for(int i = 0;i <= m;i ++) scanf("%d", &b[i]), b[i] = (b[i] + mod) % mod;
	bit = 0, tot = 1;
	while(tot <= n + m) tot <<= 1, bit ++;
	for(int i = 0;i < tot;i ++)
		r[i] = (r[i >> 1] >> 1) | ((i & 1) << (bit - 1));
	NTT(a, 1), NTT(b, 1);
	for(int i = 0;i < tot;i ++)
		a[i] = (LL)a[i] * b[i] % mod;
	NTT(a, -1);
	int inv = qpow(tot, mod - 2);
	for(int i = 0;i <= n + m;i ++)
	{
		printf("%d ", (LL)a[i] * inv % mod);
	}
	return 0;
}

多项式求逆luoguP4238 【模板】多项式乘法逆

  • 题目：给定一个多项式 $F(x)$ ，请求出一个多项式 $G(x)$， 满足 $F(x) * G(x) \equiv 1 \pmod{x^n}$。系数对 $998244353$ 取模。

  • 我们考虑倍增，设 $G_1(x)$ 满足：$G_1(x) * F(x) \equiv 1 \pmod {x^{\lceil \frac{n}{2} \rceil}}$。

  • 那么 $G(X)-G_1(x) \equiv 0 \pmod {x^{\lceil \frac{n}{2} \rceil}}$。

  • $(G(x) - G_0(x))^2 \equiv 0 \pmod {x^n}$。

  • $G^2(x) - 2G(x)G_0(x) + G_0^2(x) \equiv 0 \pmod {x^n}$。

  • 我们再根据题目 $F(x) * G(x) \equiv 1 \pmod{x^n}$ 等价变形一下。

  • $G(x) - 2G_0(x) + G_0^2(x)F(x) \equiv 0 \pmod {x^n}$。

  • $G(x) \equiv (2 - G_0(x)F(x))G_0(x) \pmod {x^n}$。

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
75
76
77
78
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 3e5 + 5, Mod = 998244353, G = 3;
int rev[N], a[N], b[N], n;
inline void calc(int bit)
{
	for(int i = 0;i < (1 << bit);i ++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
}
inline LL mod(LL x)
{
	return (x %= Mod) < 0 ? x + Mod : x;
}
LL qpow(LL a, LL k)
{
	LL res = 1;
	while(k)
	{
		if(k & 1) res = (res * a) % Mod;
		k >>= 1;
		a = (a * a) % Mod;
	}
	return res;
}
void NTT(int a[], int bit, int inv)
{
	calc(bit);
	int tot = (1 << bit);
	for(int i = 0;i < tot;i ++)
		if(rev[i] < i) swap(a[rev[i]], a[i]);
	for(int mid = 1;mid < tot; mid <<= 1)
	{
		int gn = qpow(G, (Mod - 1) / (mid << 1));
		if(inv == -1) gn = qpow(gn, Mod - 2);
		for(int i = 0; i < tot; i += mid * 2)
		{
			int g = 1;
			for(int j = 0;j < mid;j ++, g = 1ll * g * gn % Mod)
			{
				int x = a[i + j], y = 1ll * g * a[i + j + mid] % Mod;
				a[i + j] = (x + y) % Mod, a[i + j + mid] = mod(x - y);
			}
		}
	}
	if(inv == 1) return ;
	LL Inv = qpow(tot, Mod - 2);
	for(int i = 0;i < tot;i ++) a[i] = 1ll * a[i] % Mod * Inv % Mod;
}

void get_ni(int len, int a[], int b[])
{
	static int c[N];
	if(len == 1)
	{
		b[0] = qpow(a[0], Mod - 2);
		return ;
	}
	get_ni((len + 1) >> 1, a, b);
	int bit = 0, tot;
	while((1 << bit) < (len << 1)) bit ++;
	tot = (1 << bit);
	for(int i = 0;i < tot;i ++)
		if(i < len) c[i] = a[i];
		else c[i] = 0;
	NTT(c, bit, 1), NTT(b, bit, 1);
	for(int i = 0;i < tot;i ++)
		b[i] = mod(mod(2ll - 1ll * c[i] * b[i] % Mod) * b[i]);
	NTT(b, bit, -1);
	for(int i = len;i < tot;i ++) b[i] = 0;
}
int main()
{
	cin >> n;
	for(int i = 0;i < n;i ++) scanf("%lld", &a[i]);
	get_ni(n, a, b);
	for(int i = 0;i < n;i ++) printf("%d ", b[i]);
	return 0;
}

多项式除法和取模[]

  • 问题：