如题= =自用模板

dft将多项式的系数表达法转换成点对表达法 而点对的乘法是O(n)的 所以当两个多项式相乘时先把它们都转换为点对表达法 然后相乘 最后通过idft转换为系数表达式 求得我们要的值 要注意都得先补齐到2的幂次 且系数index=0为0次方从左往右递增
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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
import java.io.*;
import java.util.*;
public class Main {
static int maxn=100050*2;
static Complex[] c1=new Complex[maxn];
static Complex[] c2=new Complex[maxn];
static int[]sum=new int[200050];
public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
for(int i=0;i<maxn;i++){
c1[i]=new Complex(0,0);
c2[i]=new Complex(0,0);
}
FFT f=new FFT();
while(sc.hasNext()){
String s1=sc.next();
String s2=sc.next();
int len1=s1.length();
int len2=s2.length();
int len=1;
while(len<len1*2||len<len2*2)len=len<<1;

for(int i=0;i<len1;i++){
c1[i].r=s1.charAt(len1-1-i)-'0';
c1[i].i=0;
}
for(int i=len1;i<len;i++){
c1[i].r=0;
c1[i].i=0;
}

for(int i=0;i<len2;i++){
c2[i].r=s2.charAt(len2-1-i)-'0';
c2[i].i=0;
}
for(int i=len2;i<len;i++){
c2[i].r=0;
c2[i].i=0;
}
f.fft(c1, len, 1);
f.fft(c2, len, 1);
for(int i=0;i<len;i++){
c1[i]=c1[i].multiply(c2[i]);
}

f.fft(c1, len, -1);
for(int i=0;i<len;i++){
sum[i]=(int)(c1[i].r+0.5);
}
for(int i=0;i<len;i++){
sum[i+1]+=sum[i]/10;
sum[i]%=10;
}
StringBuilder sb=new StringBuilder();
len=len1+len2-1;
while(sum[len]<=0&&len>0)len--;
for(int i=len;i>=0;i--){
pw.print(sum[i]);
}
pw.println();
pw.flush();
}

}

}
class FFT{
final double PI=Math.acos(-1.0);
/*
* 进行FFT和IFFT前的反转变换。
* 位置i和 (i二进制反转后位置)互换
* len必须去2的幂
*/
void init(Complex []y,int len){
int i,j,k;
for(i = 1, j = len/2;i < len-1; i++){
if(i < j){
Complex temp=y[i];
y[i]=y[j];
y[j]=temp;
}
//交换互为小标反转的元素,i<j保证交换一次
//i做正常的+1,j左反转类型的+1,始终保持i和j是反转的
k = len/2;
while( j >= k){
j -= k;
k /= 2;
}
if(j < k) j += k;
}
}

/*
* 做FFT
* len必须为2^k形式,
* on==1时是DFT,on==-1时是IDFT
*/
void fft(Complex []y,int len,int on){
init(y,len);
for(int h = 2; h <= len; h <<= 1){
Complex wn=new Complex(Math.cos(-on*2*PI/h),Math.sin(-on*2*PI/h));
for(int j = 0;j < len;j+=h){
Complex w=new Complex(1,0);
for(int k = j;k < j+h/2;k++){
Complex u = y[k];
Complex t = w.multiply(y[k+h/2]);
y[k] = u.add(t);
y[k+h/2] = u.minus(t);
w = w.multiply(wn);
}
}
}
if(on == -1)
for(int i = 0;i < len;i++)
y[i].r /= len;
}


}
class Complex{
double r;
double i;
Complex(double r,double i){
this.r=r;
this.i=i;
}

Complex add(Complex b){
return new Complex(r+b.r,i+b.i);
}

Complex minus(Complex b){
return new Complex(r-b.r,i-b.i);
}

Complex multiply(Complex b){
return new Complex(r*b.r-i*b.i,r*b.i+i*b.r);
}
}