这里存一些被淘汰掉的板子之类的东西
2021-04-03
FFT
复数类操作:
1
2
3
| complex<double>m;
m.real();m.imag();
m.real(114);m.imag(514);
|
需要继续理解迭代算法.现在这就是个板子
被卡常时记得别用long double
调用FFT(A,1)将\(A\)变为\(A\)的\(DFT\),调用FFT(A,-1)求\(DFT^{-1}\).
\(A\)是复数数组,其实部初始是多项式系数.
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
| typedef double ld;
typedef complex<ld> cld;
typedef vector<cld> Poly;
const int maxn = 8E6+10;
const ld PI = acos(-1.0);
int rev[maxn];
void init(Poly & A,int n){
int size = 1;
while(size <= n)size *= 2;
A.assign(size*2,0);
}
void FFT_init(int n){
int S = log2(n);
for(int i = 0;i < n;i++)rev[i] = (rev[i>>1] >> 1) | ((i & 1) << (S - 1));
}
void FFT(Poly & A,int type){
int n = A.size();
for(int i = 0;i < n;i++)if(i < rev[i])swap(A[i],A[rev[i]]);
for(int i = 1;i < n;i *= 2){
cld Wn(cos(PI/i),type*sin(PI/i));
for(int j = 0;j < n;j += i*2){
cld W(1,0);
for(int k = 0;k < i;k++){
cld facx = A[j+k],facy = W*A[j+k+i];
A[j+k] = facx + facy;
A[j+k+i] = facx - facy;
W *= Wn;
}
}
}
if(type == -1)for(int i = 0;i < (int)A.size();i++)A[i].real((int)(A[i].real()/A.size() + 0.5));
}
|
卷积
\[
C[i] = \sum_{j = 0}^iA[j]B[i-j]
\]
卷积等同于多项式乘积
输入两个多项式\(A,B\)的系数,求出其乘积:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| signed main(){
ios::sync_with_stdio(0);
cin.tie(nullptr);
int n,m;
cin >> n >> m;
int d = n+m;
Poly A,B;
init(A,max(n,m));
init(B,max(n,m));
FFT_init(A.size());
for(int i = 0;i <= n;i++)cin >> A[i];
for(int i = 0;i <= m;i++)cin >> B[i];
FFT(A,1);
FFT(B,1);
for(int i = 0;i < (int)A.size();i++)A[i] *= B[i];
FFT(A,-1);
for(int i = 0;i <= d;i++)cout << (int)(A[i].real()/A.size() + 0.5)<< " ";
return 0;
}
|
手写复数类:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| struct node{
double x, y ;
node (double xx = 0, double yy = 0){
x = xx, y = yy ;
}
};
node operator * (node J, node Q){
return node(J.x * Q.x - J.y * Q.y , J.x * Q.y + J.y * Q.x);
}
node operator + (node J, node Q){
return node(J.x + Q.x , J.y + Q.y);
}
node operator - (node J, node Q){
return node(J.x - Q.x , J.y - Q.y );
}
|
NTT
从OI-wiki抄来的, 用法和上面的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
| typedef vector<int> Poly;
int rev[maxn];
void init(vector<int> & x,int n){
int size = 1;
while(size <= n)size *= 2;
x.assign(size*2,0);
}
void NTT_init(int lim){
for (int i = 0; i < lim; ++i) rev[i] = (i & 1) * (lim >> 1) + (rev[i >> 1] >> 1);
}
void NTT(vector<int> & A, int opt) {
int lim = A.size();
int i, j, k, m, gn, g, tmp;
for(i = 0; i < lim; ++i)if (rev[i] < i) swap(A[i], A[rev[i]]);
for(m = 2; m <= lim; m <<= 1) {
k = m >> 1;
gn = Pow(3,(p - 1) / m);
for(i = 0; i < lim; i += m) {
g = 1;
for (j = 0; j < k; ++j, g = 1ll * g * gn % p) {
tmp = 1ll * A[i + j + k] * g % p;
A[i + j + k] = (A[i + j] - tmp + p) % p;
A[i + j] = (A[i + j] + tmp) % p;
}
}
}
if(opt == -1){
auto it = A.begin();it++;
reverse(it,A.end());
int inv = Pow(lim,p-2);
for(i = 0; i < lim; ++i) A[i] = 1ll * A[i] * inv % p;
}
}
|
与FFT的区别在点值表示法相乘时, NTT需要取模. 另外注意原根需与模数对应
1
| for(int i = 0;i < (int)A.size();i++)A[i] = 1ll*A[i]*B[i]%p;
|