题目链接

A * B Problem Plus

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 12490    Accepted Submission(s): 2206

Problem Description
Calculate A * B.
Input
Each line will contain two integers A and B. Process to end of file.

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

Output
For each case, output A * B in one line.
Sample Input
1
2
1000
2
Sample Output
2
2000
初学FFT,根本不懂怎么实现的。直接套模板
Accepted Code:
 #include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <bitset>
#include <complex>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define all(o) (o).begin(), (o).end()
#define rall(o) (o).rbegin(), ((o).rend())
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; } typedef long double Num; //??????long double?????
const Num PI = .141592653589793238462643383279L;
typedef complex<Num> Complex;
//n?????
//a?????
void fft_main(int n, Num theta, Complex a[]) {
for(int m = n; m >= ; m >>= ) {
int mh = m >> ;
Complex thetaI = Complex(, theta);
rep(i, mh) {
Complex w = exp((Num)i*thetaI);
for(int j = i; j < n; j += m) {
int k = j + mh;
Complex x = a[j] - a[k];
a[j] += a[k];
a[k] = w * x;
}
}
theta *= ;
}
int i = ;
reu(j, , n-) {
for(int k = n >> ; k > (i ^= k); k >>= ) ;
if(j < i) swap(a[i], a[j]);
}
} void fft(int n, Complex a[]) { fft_main(n, * PI / n, a); }
void inverse_fft(int n, Complex a[]) { fft_main(n, - * PI / n, a); } void convolution(vector<Complex> &v, vector<Complex> &w) {
int n = , vwn = v.size() + w.size() - ;
while(n < vwn) n <<= ;
v.resize(n), w.resize(n);
fft(n, &v[]);
fft(n, &w[]);
rep(i, n) v[i] *= w[i];
inverse_fft(n, &v[]);
rep(i, n) v[i] /= n;
} const int maxn = ;
vector<int> ans;
char s1[maxn], s2[maxn]; void solve(vector<int> &res) {
//cerr << s1 << s2;
int len1 = strlen(s1), len2 = strlen(s2);
for (int i = ; i < len1; i++) s1[i] -= '';
for (int i = ; i < len2; i++) s2[i] -= '';
vector<Complex> Lc(len1), Rc(len2);
for (int i = ; i < len1; i++) Lc[i] = Complex(s1[len1-i-], );
for (int i = ; i < len2; i++) Rc[i] = Complex(s2[len2-i-], );
convolution(Lc, Rc);
int n = len1 + len2 - ;
res.resize(n);
rep(i, n) res[i] = Lc[i].real() + .;
} int main(void) {
while (~scanf("%s %s", s1, s2)) {
solve(ans);
ans.resize(ans.size() << );
for (int i = ; i < ans.size(); i++) {
ans[i+] += ans[i] / ;
ans[i] %= ;
}
int high = ans.size() - ;
while (high > && !ans[high]) high--;
for (int i = high; i >= ; i--) putchar(ans[i] + '');
putchar('\n');
}
return ;
}

最新文章

  1. 【翻译】MongoDB指南/CRUD操作(四)
  2. GeoServer中WMS、WFS的请求规范
  3. php知识分享
  4. jdk的安装及配置
  5. tomcat切割日志的shell脚本
  6. Unity3D]引擎崩溃、异常、警告、BUG与提示总结及解决方法
  7. svn服务端hooks钩子可用于多项目自动同步
  8. poj3254
  9. jQuery粘性跟随滚动条滚动的导航栏源代码下载
  10. Java中多线程原理详解
  11. 【3D计算机图形学】变换矩阵、欧拉角、四元数
  12. asp.net mvc webapi 实用的接口加密方法
  13. Java calendar获取月份注意事项
  14. PERL学习笔记---正则表达式的应用
  15. 弹筐里同一个按钮判断是从哪里点击过来的form
  16. ES6使用Set实现数组去重
  17. Django之Models(二)
  18. 微信小程序的布局css样式
  19. ASP.NET CORE 2.0 发布到IIS,IIS如何设置环境变量来区分生产环境和测试环境
  20. python自带的调试器

热门文章

  1. 踩坑记-java mysql 新增获取主键、DIY主键、UUID
  2. 网络编程(client发信息给server)
  3. 日志服务与SIEM(如Splunk)集成方案实战
  4. CF1163E Magical Permutation
  5. docker 安装 ElasticSearch
  6. Git命令汇总(转)
  7. SPSS输出结果统计表与统计图的专业性编辑及三线表定制格式
  8. XJOI夏令营501训练1——分配工作
  9. “Error: Encountered an improper argument”的解决方法
  10. 《DSP using MATLAB》Problem 8.13