首页 > ACM题库 > HDU-杭电 > HDU 1402 A * B Problem Plus[解题报告] C++
2013
12-09

HDU 1402 A * B Problem Plus[解题报告] C++

A * B Problem Plus

问题描述 :

Calculate A * B.

输入:

Each line will contain two integers A and B. Process to end of file.

Note: the length of each integer will not exceed 50000.

输出:

For each case, output A * B in one line.

样例输入:

1
2
1000
2

样例输出:

2
2000

此处介绍另一种方法来解决这题,也就是FFT(快速傅里叶变换)

 

如果是乘法,位数为n和位数为m的相乘,需要n*m次的乘法运算。

 

FFT在数字信号处理学过,但是第一次用来做这类题目,神奇啊。

 

乘法其实就是做线性卷积。

 

用DFT得方法可以求循环卷积,但是当循环卷积长度LN+M-1,就可以做线性卷积了。

 

使用FFT将两个数列转换成傅里叶域,在这的乘积就是时域的卷积。

 

 

 

给几个学习的链接吧:

 

http://wenku.baidu.com/view/8bfb0bd476a20029bd642d85.html  (这主要看那个FFT的流程图

 

http://wlsyzx.yzu.edu.cn/kcwz/szxhcl/kechenneirong/jiaoan/jiaoan3.htm   这有DFT的原理。

#include<iostream>
 #include<stdio.h>
 #include<algorithm>
 #include<iomanip>
 #include<cmath>
 #include<cstring>
 #include<vector>
 #define ll __int64
 #define pi acos(-1.0)
 using namespace std;
 const int MAX = 200002;
 //复数结构体
 struct complex{
     double r,i;
     complex(double R=0,double I=0){
         r=R;i=I;
     }
     complex operator+(const complex &a){
         return complex(r+a.r,i+a.i);
     }
     complex operator-(const complex &a){
         return complex(r-a.r,i-a.i);
     }
     complex operator*(const complex &a){
         return complex(r*a.r-i*a.i,r*a.i+i*a.r);
     }
 };
 /*
  *进行FFT和IFFT前的反转变换
  *位置i和i的二进制反转后位置互换,(如001反转后就是100)
  *len必须去2的幂
  */
 void change(complex x[],int len){
     int i,j,k;
     for(i = 1, j = len/2; i <len-1; i++){
         if (i < j) swap(x[i],x[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^n形式,不足则补0
  *on=1时是DFT,on=-1时是IDFT
  */
 void fft (complex x[],int len,int on){
     change(x,len);
     for (int i=2;i<=len;i<<=1){
         complex wn(cos(-on*2*pi/i),sin(-on*2*pi/i));
         for (int j=0;j<len;j+=i){
             complex w(1,0);
             for (int k=j;k<j+i/2;k++){
                 complex u = x[k];
                 complex t = w*x[k+i/2];
                 x[k] = u+t;
                 x[k+i/2] = u-t;
                 w = w*wn;
             }
         }
     }
     if (on == -1){
         for (int i=0;i<len;i++){
             x[i].r /= len;
         }
     }
 }
 complex x1[MAX],x2[MAX];
 char str1[MAX/2],str2[MAX/2];
 ll num[MAX],sum[MAX];
 int main()
 {
     int i,j,k,len1,len2,len;
     while(scanf("%s%s",&str1,&str2)!=EOF){
         len1 = strlen(str1);
         len2 = strlen(str2);
         len = 1;
         while (len < 2*len1 || len < 2*len2) len<<=1;
         for (i=0;i<len1;i++){
             x1[i] = complex(str1[len1-1-i]-'0',0);
         }
         for (i=len1;i<len;i++){
             x1[i] = complex(0,0);
         }
         for (i=0;i<len2;i++){
             x2[i] = complex(str2[len2-1-i]-'0',0);
         }
         for (i=len2;i<len;i++){
             x2[i] = complex(0,0);
         }
         fft(x1,len,1);
         fft(x2,len,1);
         for (i=0;i<len;i++){
             x1[i] = x1[i]*x2[i];
         }
         fft(x1,len,-1);
         for (i=0;i<len;i++){
             sum[i] = (int)(x1[i].r+0.5);
         }
         for (i=0;i<len;i++){
             sum[i+1]+=sum[i]/10;
             sum[i]%=10;
         }
         len = len1+len2-1;
         while (sum[len]<=0 && len>0) len--;
         for (i=len;i>=0;i--){
             printf("%c",sum[i]+'0');
         }
         printf("\n");
     }
     return 0;
 }

 

 

解题报告转自:http://www.cnblogs.com/xin-hua/p/3216830.html


  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

  2. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮