做多项式题就像嗑药，出多项式题就像贩毒。
多项式表示
讲到多项式有系数表示法和点表示法两种情况，其关系是在于：
如果有一个 次多项式 ，其点表示法为 ，有：
多项式卷积
有三个不定次多项式 ，如果有 ，则有：
这就是多项式卷积，通俗来讲就是多项式乘法。暴力计算时间复杂度为 ，通过 可以优化到 。
关于傅里叶变换
在求多项式卷积的时候，傅里叶变换经历了三个过程：
- 快速傅里叶变换（）：用一组特殊点（复数单位根）快速计算出点表示法。
- 离散傅里叶变换（）：通过奇偶性分类让一组单位根快速计算其 值。
- 离散傅里叶逆变换（）：通过点表示法逆转换为系数表示法。
时间分别是 。
而通过用迭代的方法来代替 的递归，这个优化称为蝴蝶变换。
为什么可以使用复数单位根？
在上一章我们已经知道了复数单位根的定义，所以这里不多赘述。
根据欧拉公式，可以得到 。
所以，有 ，因此，我们能够在很快的时间内使用 ，以免不必要的麻烦。
这是 优化多项式卷积的过程，我们在上一章详细讲过。
原根
阶
由欧拉定理可知：。因此，存在最小正整数 使得 ，这个时候， 被称为 模 的阶，记作 。
关于阶有许多性质：
- 模 两两不同余。
- 若 ，则有 。
- 若 ，则有 。
- 设 ，
则有：，即两者互为充要条件。
- 设 ，
则有：。
最后两个性质在阶的四则运算中发挥了重要作用。
原根的定义
设 ，若有 ，且 ，则 是模 的原根。
用人话来讲，如果存在一个数 使得 在模 意义下两两不同，则 是 的原根。
原根判定定理
我们这里只考虑 的情况（毕竟 手玩都可以解决）。设 ，则 是模 的原根的充要条件是：对于 的任意质因子 都满足 。
其证明需要用到裴蜀定理和欧拉定理，可利用反证法解决。
原根个数定理
对于一个数 ，如果其存在原根，则其原根个数为 。
证明
若 有原根 ，则：
当 时，则有 ，即 也是 的原根。
而满足 且 的 有 个，所以原根亦如此。
证毕
原根存在定理
一个数 存在原根当且仅当 ，其中 为奇质数，。
其证明需要 个步骤，较为麻烦，这里不进行讲述，可见 的详细证明。
最小原根数量级定理
若 有原根，则其最小原根 满足 。
这个定理由王元在 年提出，为暴力计算原根提供了依据。
数论变换
考虑下面一个问题：
题目简介
对于一个 次多项式 和一个 次多项式 ，有 ，给定一个 ，求 对 取模的结果。
数据范围：， 为质数。
显然，对于在 double 下使用复数计算的 并不能很好地计算取模意义下的多项式卷积问题，那么，就要清楚本章的主角——数论变换（）了。
在 中，我们用原根代替复数单位元进行运算，以避免精度出错和无法取模的问题。
为什么原根可以代替复数单位元
在 的计算中，我们用到了复数单位元的几条性质：
- 对于 ，当 时除外，保证了点值的合法性。
- ，用于分治。
- ，用于分治。
- 当 时，，用于逆变换。
而同样的，原根也具有相同的性质，我们设
两者结合，可以得到：
然后我们用这些玩意儿代替原来的复数即可。代码结构与 极其相似。
一般情况下， 的常数会比 小很多，所以很多多项式题都是用 来做的。
一般取质数 为 有：
或者
。
参考代码
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
x=0;
char ch=getchar(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=4e6+10;
const int P=998244353,G=3,InvG=332748118;
int N,M;
inline ll qPow(ll a,ll b)
{
ll res=1;
while(b)
{
if(b&1) res=res*a%P;
a=a*a%P;b>>=1;
}
return res;
}
ll A[MAXN],B[MAXN];
int Tot,Bit,Rev[MAXN];
inline void NTT(ll a[],int inv)
{
for(int i=0;i<Tot;++i)
if(i<Rev[i]) std::swap(a[i],a[Rev[i]]);
for(int mid=1;mid<Tot;mid<<=1)
{
auto w1=qPow(inv==1?G:InvG,(P-1)/(mid<<1));
for(int i=0;i<Tot;i+=mid*2)
{
auto wk=1;
for(int j=0;j<mid;++j,wk=wk*w1%P)
{
auto x=a[i+j],y=a[i+j+mid]*wk%P;
a[i+j]=(x+y)%P,a[i+j+mid]=(x-y+P)%P;
}
}
}
if(inv==-1)
{
ll iv=qPow(Tot,P-2);
for(int i=0;i<Tot;++i) a[i]=a[i]*iv%P;
}
}
int main()
{
read(N,M);
for(int i=0;i<=N;++i) read(A[i]);
for(int i=0;i<=M;++i) read(B[i]);
while((1<<Bit)<=N+M) ++Bit;
Tot=1<<Bit;
for(int i=0;i<Tot;++i) Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(Bit-1));
NTT(A,1),NTT(B,1);
for(int i=0;i<Tot;++i) A[i]=A[i]*B[i]%P;
NTT(A,-1);
for(int i=0;i<=N+M;++i) write(A[i]%P,' ');
return 0;
}
|
优化高精度乘法也和上面的代码实现相同，不过多了一个进位操作而已。其构造也与 类似。
接下来，你可以解锁下列章节：