hdu 1402 FFT
发布时间:2020-12-14 03:06:42 所属栏目:大数据 来源:网络整理
导读:就是求两个长度为50000的数相乘。 第一次用了FFT来搞这种题目。 接下来还要训练几道这样的题目。 代码: #include iostream#include algorithm#include cstdio#include string#include cstring#include cmath#include vector#include list#include map#inclu
就是求两个长度为50000的数相乘。 第一次用了FFT来搞这种题目。 接下来还要训练几道这样的题目。 代码: #include <iostream> #include <algorithm> #include <cstdio> #include <string> #include <cstring> #include <cmath> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <functional> #include <sstream> #include <iomanip> #include <cmath> #include <cstdlib> #include <ctime> //#pragma comment(linker,"/STACK:102400000,102400000") typedef long long ll; #define INF 1e9 const int maxn = 200005; //#define mod 1000000007 #define eps 1e-7 #define pi 3.1415926535897932384626433 #define rep(i,n) for(int i=0;i<n;i++) #define rep1(i,n) for(int i=1;i<=n;i++) #define scan(n) scanf("%d",&n) #define scanll(n) scanf("%I64d",&n) #define scan2(n,m) scanf("%d%d",&n,&m) #define scans(s) scanf("%s",s); #define ini(a) memset(a,sizeof(a)) #define out(n) printf("%dn",n) //ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b);} using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 const double PI = acos(-1.0); //复数结构体 struct complex { double r,i; complex(double _r = 0.0,double _i = 0.0) { r = _r; i = _i; } complex operator +(const complex &b) { return complex(r+b.r,i+b.i); } complex operator -(const complex &b) { return complex(r-b.r,i-b.i); } complex operator *(const complex &b) { return complex(r*b.r-i*b.i,r*b.i+i*b.r); } }; /* * 进行FFT和IFFT前的反转变换。 * 位置i和 (i二进制反转后位置)互换 * len必须去2的幂 */ void change(complex y[],int len) { int i,j,k; for(i = 1,j = len/2;i < len-1; i++) { if(i < j)swap(y[i],y[j]); //交换互为小标反转的元素,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) { change(y,len); for(int h = 2; h <= len; h <<= 1) { complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h)); for(int j = 0;j < len;j+=h) { complex w(1,0); for(int k = j;k < j+h/2;k++) { complex u = y[k]; complex t = w*y[k+h/2]; y[k] = u+t; y[k+h/2] = u-t; w = w*wn; } } } if(on == -1) for(int i = 0;i < len;i++) y[i].r /= len; } char a[maxn],b[maxn]; complex A[maxn],B[maxn]; int ans[maxn]; int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); #endif while(~scanf("%s%s",a,b)) { int l1 = strlen(a),l2 = strlen(b); int n = 1; while(n < max(l1,l2) * 2) n <<= 1; //n至少为maxl的两倍 ini(A); ini(B); ini(ans); rep(i,n) { if(i < l1) A[i] = complex(a[l1 - i - 1] - '0',0); //高位在前,这样FFT后高位在后 else A[i] = complex(0,0); } rep(i,n) { if(i < l2) B[i] = complex(b[l2 - i - 1] - '0',0); else B[i] = complex(0,0); } FFT(A,n,1); FFT(B,1); rep(i,n) A[i] = A[i] * B[i]; FFT(A,-1); rep(i,n) ans[i] = (int)(A[i].r + 0.5); for(int i = 0;i < n; i++) { ans[i+1] += ans[i] / 10; //向上进位 ans[i] %= 10; //本身保留个位 } for(; !ans[n]; n--); //消去前导0 if(n < 0){ puts("0"); continue; } for(int i = n;i >= 0; i--) printf("%d",ans[i]); puts(""); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |