FFT/NTT [51Nod 1028] 大数乘法 V2

时间:2021-04-07 10:13:51

题目链接:51Nod 传送门

没压位,效率会低一点

1.FFT

FFT/NTT [51Nod 1028] 大数乘法 V2

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN = 1<<18;
const double Pi = acos(-1.0); struct complex
{
double r, i;
complex(double _r=0, double _i=0):r(_r), i(_i){}
complex operator +(const complex &t)const
{
return complex(r + t.r, i + t.i);
}
complex operator -(const complex &t)const
{
return complex(r - t.r, i - t.i);
}
complex operator *(const complex &t)const
{
return complex(r*t.r - i*t.i, r*t.i + t.r*i);
}
}a1[MAXN], a2[MAXN], w, wn;
char s1[MAXN], s2[MAXN];
int n, len1, len2, ans[MAXN]; inline void change(complex arr[], int len)
{
for(int i = 1, j = len/2, k; i < len-1; ++i)
{
if(i < j) swap(arr[i], arr[j]);
for(k = len/2; k <= j; j-=k, k>>=1);
j += k;
}
} inline void FFT(complex arr[], int len, int flg)
{
change(arr, len);
for(int i = 2; i <= len; i<<=1)
{
wn = complex(cos(Pi*flg*2/i), sin(Pi*flg*2/i));
for(int j = 0; j < len; j+=i)
{
w = complex(1, 0);
for(int k = j; k < j + i/2; ++k)
{
complex wA1 = w * arr[k + i/2];
complex A0 = arr[k];
arr[k] = A0 + wA1;
arr[k + i/2] = A0 - wA1;
w = w * wn;
}
}
}
if(flg == -1)
for(int i = 0; i < len; ++i)
arr[i].r /= len;
} int main()
{
scanf("%s", s1), len1 = strlen(s1);
scanf("%s", s2), len2 = strlen(s2);
int len = len1 + len2;
for(n = 1; n < len; n<<=1); for(int i = 0; i < len1; ++i) a1[i] = complex((double)(s1[i] - '0'), 0);
for(int i = len1; i < n; ++i) a1[i] = complex();
FFT(a1, n, 1); for(int i = 0; i < len2; ++i) a2[i] = complex((double)(s2[i] - '0'), 0);
for(int i = len2; i < n; ++i) a2[i] = complex();
FFT(a2, n, 1); for(int i = 0; i < n; ++i) a2[i] = a1[i] * a2[i];
FFT(a2, n, -1); for(int i = 0; i < len1+len2-1; ++i)
ans[i] = (int)(a2[i].r + 0.5); for(int i = len1+len2-2; i; --i)
{
ans[i-1] += ans[i]/10;
ans[i] %= 10;
}
int i; for(i = 0; !ans[i] && i < len1+len2-1; ++i); if(i == len1+len2-1) putchar('0');
else while(i < len1+len2-1) printf("%d",ans[i++]);
putchar(10);
}

2.NTT

FFT/NTT [51Nod 1028] 大数乘法 V2

似乎并没有比FFT快

空间到是少了不少

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 1<<18;
const int mod = 998244353, G = 3;
char str1[MAXN], str2[MAXN];
int a1[MAXN], a2[MAXN]; inline void change(int arr[], const int& len)
{
for(register int i = 1, j = len/2; i < len-1; ++i)
{
if(i < j) swap(arr[i], arr[j]);
int k = len/2;
while(j >= k) j -= k, k>>=1;
j += k; //-.-写成了减样例半天没调过
}
} inline int qmul(int a, int b)
{
int ret = 1;
while(b)
{
if(b & 1) ret = (LL)ret * a % mod;
a = (LL)a * a % mod; b>>=1;
}
return ret;
} inline void NTT(int arr[], const int& len, const int& flg)
{
change(arr, len);
for(int i = 2, w, wn; i <= len; i<<=1)
{
if(~flg) wn = qmul(G, (mod-1)/i);
else wn = qmul(G, mod-1 - (mod-1)/i);
for(int j = 0; j < len; j += i)
{
w = 1;
for(int k = j; k < j + i/2; ++k)
{
int A0 = arr[k];
int wA1 = (LL)w * arr[k + i/2] % mod;
arr[k] = (A0 + wA1) % mod;
arr[k + i/2] = ((A0 - wA1) % mod + mod) % mod; //注意爆负 w = (LL)w * wn % mod;
}
}
}
if(flg == -1)
{
int inv = qmul(len, mod-2);
for(int i = 0; i < len; ++i)
arr[i] = (LL)arr[i] * inv % mod;
}
} int main ()
{
scanf("%s%s", str1, str2);
int len1 = strlen(str1);
int len2 = strlen(str2);
int ml = len1 + len2, len = 1;
while(len < ml) len<<=1; for(int i = 0; i < len1; ++i) a1[i] = str1[i] - '0';
for(int i = len1; i < len; ++i) a1[i] = 0;
for(int i = 0; i < len2; ++i) a2[i] = str2[i] - '0';
for(int i = len2; i < len; ++i) a2[i] = 0; NTT(a1, len, 1), NTT(a2, len, 1); for(int i = 0; i < len; ++i) a2[i] = (LL)a1[i] * a2[i] % mod; NTT(a2, len, -1); for(int i = len1+len2-2; i; --i)
a2[i-1] += a2[i] / 10, a2[i] %= 10; int i = 0;
while(i < len1+len2-1 && !a2[i]) ++i; if(i == len1+len2-1) puts("0");
else while(i < len1+len2-1) printf("%d", a2[i++]);
putchar(10);
}