洛谷P1919 【模板】A*B Problem升级版 题解(FFT的第一次实战)

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

刚学了FFT,我们来刷一道模板题。

题目描述

给定两个长度为 n 的两个十进制数,求它们的乘积。

n<=100000

如果用 n^2 暴力,肯定会 TLE。

我们把这两个数看成一个多项式。

f(x)=a0+a1*101+a2*102+a3*103+ ...... +an-1*10n-1

然后就可以愉快的FFT求解了!!

 #include<iostream>
#include<cmath>
#include<complex>
#include<cstdio>
using namespace std; const double PI=acos(-);
typedef complex<double> cmplx;
int rev[];
cmplx a[],b[];
int n,bit=,output[];
char s1[],s2[]; void get_rev(){
for(int i=;i<bit;i++)
rev[i]=(rev[i>>]>>)|(bit>>)*(i&);
} void FFT(cmplx *a,int dft){
for(int i=;i<bit;i++)
if(i<rev[i])swap(a[i],a[rev[i]]);
for(int i=;i<bit;i<<=){
cmplx W=exp(cmplx(,dft*PI/i));
for(int j=;j<bit;j+=i<<){
cmplx w(,);
for(int k=j;k<j+i;k++,w*=W){
cmplx x=a[k];
cmplx y=w*a[k+i];
a[k]=x+y;
a[k+i]=x-y;
}
}
}
if(!~dft)for(int i=;i<bit;i++)a[i]/=bit;
} int main(){
scanf("%d%s%s",&n,s1,s2);
for(int i=;(<<i)<=*n;i++)bit<<=;
for(int i=;i<n;i++){
a[i]=s1[n-i-]-'';
b[i]=s2[n-i-]-'';
}
get_rev();
FFT(a,),FFT(b,);
for(int i=;i<bit;i++)a[i]=a[i]*b[i];
FFT(a,-);
for(int i=;i<bit;i++){ //确保输出为十进制
output[i]+=a[i].real()+0.5;
output[i+]+=output[i]/;
output[i]%=;
}
bool check=false;
for(int i=n<<;i>=;i--){ //去前导零输出
if(check||output[i]){
printf("%d",output[i]);
check=true;
}
}
if(!check)printf("");
}

FFT学习笔记

上一篇:nginx/php的redis模块扩展


下一篇:怎么才能快速提高小程序留存率!