HDU1402 A * B Problem Plus 大数乘法 FFT(快速傅里叶变换)优化
发布时间:2020-12-14 01:37:30 所属栏目:大数据 来源:网络整理
导读:HDU1402 A * B Problem Plus 大数乘法 FFT(快速傅里叶变换)优化 题目 长度不超过5000,据称高精度会TLE,必须 O ( n l o g n ) ,FFT首敲。 代码 bit_reverse_swap(a,n) 参考自算法导论30.3的迭代实现,非递归方式完成下图过程。 #include cstdio #include c
HDU1402 A * B Problem Plus 大数乘法 FFT(快速傅里叶变换)优化题目长度不超过5000,据称高精度会TLE,必须
代码bit_reverse_swap(a,n)参考自算法导论30.3的迭代实现,非递归方式完成下图过程。 #include <cstdio>
#include <cmath>
#include <complex>
#include <cstring>
using namespace std;
const double PI(acos(-1.0));
typedef complex<double> C;
const int N = (1<<17);
int ans[N];
C a[N],b[N];
char s[N],t[N];
void bit_reverse_swap(C *a,int n)
{
for(int i = 1,j = n>>1,k; i < n-1; ++i)
{
if(i < j) swap(a[i],a[j]);
//tricky
for(k = n>>1; j >= k; j -= k,k >>= 1) //inspect the highest "1"
;
j+=k;
}
}
void FFT(C* a,int n,int t)
{
bit_reverse_swap(a,n);
for(int i = 2; i <= n; i <<= 1)
{
C wi(cos(2.0*t*PI/i),sin(2.0*t*PI/i));
for (int j = 0; j < n; j += i)
{
C w(1);
for (int k = j,h = i >> 1; k < j + h; ++k)
{
C t = w*a[k+h],u = a[k];
a[k] = u + t;
a[k+h] = u - t;
w *= wi;
}
}
}
if (t == -1)
{
for (int i = 0; i < n; ++i)
{
a[i] /= n;
}
}
}
int trans(int x)
{
return 1 << int(ceil(log(x)/log(2) - 1e-9)); //math.h/log() 以e为底
}
int main()
{
int n,m,l;
for(; ~scanf("%s%s",s,t); )
{
n = strlen(s);
m = strlen(t);
l = trans(n + m - 1); //n次*m次不超过n+m-1次
for (int i = 0; i < n; ++i)
a[i] = C(s[n-1-i]-'0');
for (int i = n; i < l; ++i)
a[i] = C(0);
for (int i = 0; i < m; ++i)
b[i] = C(t[m-1-i]-'0');
for (int i = m; i < l; ++i)
b[i] = C(0);
FFT(a,l,1);//把A和B换成点值表达
FFT(b,1);
for (int i = 0; i < l; ++i)//点值做乘法
a[i] *= b[i];
FFT(a,-1);//逆DFT
for (int i = 0; i < l; ++i)
ans[i] = (int)(a[i].real() + 0.5);
ans[l] = 0; // error-prone :'l' -> '1'
for (int i = 0; i < l; ++i)
{
ans[i+1] += ans[i] / 10;
ans[i] %= 10;
}
int p = l;
for(; p && !ans[p]; --p);
for(; ~p; putchar(ans[p--] + '0'));
puts("");
}
return 0;
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |