题解 P1919 【模板】A*B Problem升级版(FFT快速傅里叶)

皎月半洒花

2018-07-04 16:51:44

Solution

这个题是不是一直少一篇正常的题解啊 $\rm QAQ$ 感觉为什么其他同样是 $FFT$ 的码风这么不正经啊 $\rm QAQ$ $py$ 好用但是 ~~圈钱组织~~ CCF不承认啊 $\rm QAQ$ 所以我们还是老老实实地 $FFT$ 吧 = = ## 正确性: 对于每一个 $n$ 位的十进制数,我们可以看做一个 $n-1$ 次多项式 $A$,满足 $$ A(x) =a_0+a_1 \times 10+a_2\times10^2 \cdots +a_{n-1}\times10^{n-1} $$ 那么对于两个大整数相乘,我们就可以卷起来辣$qwq$ ## 小细节: - 不要忘记进位$qwq$ - 不要忘了要保证数位上的单调性,因为我们普通的$FFT$卷积时,高次项一定由低次项得到,放在这里也一样,所以我们要倒序存储。 - 不会$FFT$的,戳这里[Link](https://www.cnblogs.com/pks-t/p/9251147.html) ```cpp #include <cmath> #include <cstdio> #include <iostream> #define il inline #define MAXN 3000100 using namespace std ; char s1[MAXN], s2[MAXN] ; int N, M, K, res = 0, ans[MAXN], AA, BB ; int i, j, k, l, Lim = 1, L, R[MAXN] ; const double Pi = acos(-1.0) ; struct node{ double x, y ; node (double xx = 0, double yy = 0){ x = xx, y = yy ; } }A[MAXN], B[MAXN] ; 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 ); } il int qr(){ int k = 0, f = 1 ; char c = getchar() ; while(!isdigit(c)){if(c == '-') f = -1 ;c = getchar() ;} while(isdigit(c)) k = (k << 1) + (k << 3) + c - 48 ,c = getchar() ; return k * f ; } il void FFT(node *J, double flag){ for(i = 0; i < Lim; i ++) if(i < R[i]) swap(J[i], J[R[i]]) ; for(j = 1; j < Lim; j <<= 1){ node T(cos(Pi / j), flag * sin(Pi / j)) ; for(k = 0; k < Lim; k += (j << 1) ){ node t(1, 0) ; for(l = 0 ; l < j; l ++, t = t * T){ node Nx = J[k + l], Ny = t * J[k + j + l] ; J[k + l] = Nx + Ny ; J[k + j + l] = Nx - Ny ; } } } } int main(){ N = qr() ; scanf("%s%s", s1, s2) ; for(i = N - 1; i >= 0; i --) A[AA ++].x = s1[i] - 48; for(i = N - 1; i >= 0; i --) B[BB ++].x = s2[i] - 48; while(Lim < N + N ) Lim <<= 1, L ++ ; for(i = 0; i <= Lim; i ++ ) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (L - 1)) ; FFT(A, 1), FFT(B, 1) ; for(i = 0; i <= Lim; i ++) A[i] = A[i] * B[i] ; FFT(A, -1) ; int tot = 0 ; for(i = 0; i <= Lim; i++) { ans[i] += (int) (A[i].x / Lim + 0.5) ; if(ans[i] >= 10) ans[i + 1] += ans[i] / 10, ans[i] %= 10, Lim += (i == Lim); } while(!ans[Lim] && Lim >= 1) Lim -- ; Lim ++ ; while( -- Lim >= 0) cout << ans[Lim] ; return 0 ; } ```