P1919-【模板】A*B Problem 升级版（FFT 快速傅里叶）
题目:
题目描述:
给你两个正整数 $a,b$，求 $a \times b$。
输入格式:
第一行一个正整数，表示 $a$；
第二行一个正整数，表示 $b$。
输出格式:
输出一行一个整数表示答案。
样例:
样例输入 1:
样例输出 1:
思路:
实现:
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
| #include "ybwhead/ios.h"
// #define int long long
string s, s1;
int lim;
const int maxn = 3e6 + 10;
const long long mod=998244353;
int r[maxn];
long long a[maxn];
long long b[maxn];
long long ksm(long long a, int n)
{
long long ans=1;
while (n)
{
if (n&1)ans=ans*a%mod;
a=(a*a)%mod;
n>>=1;
}
return ans;
}
const long long g=3, gi=ksm(3, mod-2);
void NTT(long long a[], long long x)
{
for (int i=1;i<=lim;i++)
{
// yout<<i-1<<" "<<r[i-1]<<endl;
// yout<<i<<' '<<r[i-1]+1<<endl;
if (i-1<r[i-1]+1)swap(a[i], a[r[i-1]+1]);
}
for (int o=1;o<lim;o<<=1)
{
long long wn=ksm(x, (mod-1)/(o<<1));
for (int i=1;i<=lim;i+=o<<1)
{
long long w=1;
for (int j=0;j<o;j++, w=w*wn%mod)
{
long long x=a[i+j], y=a[i+j+o]*w%mod;
// cout<<x<<' '<<y<<endl;
a[i+j]=(x+y)%mod;
a[i+j+o]=(long long)(x-y+mod)%mod;
}
}
}
}
signed main()
{
yin >> s >> s1;
int n = s.size(), m = s1.size();
for (int i = 1; i <= n; i++)
a[i] = s[n-i] - '0';
for (int i = 1; i <= m; i++)
b[i] = s1[m-i] - '0';
int l=0;
lim=1;
while (lim < n + m)
lim <<= 1, ++l;
for (int i = 0; i < lim; i++)
{
r[i] = (r[i >> 1]>>1) | ((i & 1) << (l - 1));
}
// puts("!!!");
NTT(a, g);
NTT(b, g);
// puts("!!!");
for (int i = 1; i <= lim; i++)
{
a[i] *= b[i];
a[i]%=mod;
// cout<<a[i]<<" "<<b[i]<<endl;
}
// cout<<gi<<endl;
NTT(a, gi);
long long inv=ksm(lim, mod-2);
for (int i=1;i<=lim;i++)
{
a[i]=(a[i]*inv)%mod;
// cout<<a[i]<<endl;
}
for (int i=1;i<=lim;i++)
{
a[i+1]+=a[i]/10;
a[i]%=10;
}
++lim;
while (!a[lim]&&lim)lim--;
if (!lim)puts("0");
else for (int i=lim;i>=1;i--)yout<<a[i];
yout<<endl;
return 0;
}
|