因为刚学fft,想拿这题练练手,结果WA了个爽= =。

  总结几点犯的错误:

  1.要注意处理前导零的问题。

  2.一定要注意数组大小的问题。(前一个fft的题因为没用到b数组,所以b就没管,这里使用了b数组,结果忘记给其大小乘以4倍了)

  代码如下:

 #include<bits/stdc++.h>
using namespace std;
const double pi = atan(1.0)*;
const int N = 5e4 + ;
typedef long long ll; struct Complex {
double x,y;
Complex(double _x=,double _y=)
:x(_x),y(_y) {}
Complex operator + (Complex &tt) { return Complex(x+tt.x,y+tt.y); }
Complex operator - (Complex &tt) { return Complex(x-tt.x,y-tt.y); }
Complex operator * (Complex &tt) { return Complex(x*tt.x-y*tt.y,x*tt.y+y*tt.x); }
};
Complex a[N*],b[N*];
void fft(Complex *a, int n, int rev) {
// n是(大于等于相乘的两个数组长度)2的幂次 ; 比如长度是5 ,那么 n = 8 2^2 < 5 2^3 > 5
// 从0开始表示长度,对a进行操作
// rev==1进行DFT,==-1进行IDFT
for (int i = ,j = ; i < n; ++ i) {
for (int k = n>>; k > (j^=k); k >>= );
if (i<j) std::swap(a[i],a[j]);
}
for (int m = ; m <= n; m <<= ) {
Complex wm(cos(*pi*rev/m),sin(*pi*rev/m));
for (int i = ; i < n; i += m) {
Complex w(1.0,0.0);
for (int j = i; j < i+m/; ++ j) {
Complex t = w*a[j+m/];
a[j+m/] = a[j] - t;
a[j] = a[j] + t;
w = w * wm;
}
}
}
if (rev==-) {
for (int i = ; i < n; ++ i) a[i].x /= n,a[i].y /= n;
}
} char s[N], t[N];
int c[N*]; int main(){
/*a[0] = Complex(0,0); // a[0]: x的0次项。
a[1] = Complex(1,0);
a[2] = Complex(2,0);
a[3] = Complex(3,0); b[0] = Complex(3,0);
b[1] = Complex(2,0);
b[2] = Complex(1,0);
b[3] = Complex(0,0);
fft(a,8,1);
fft(b,8,1);
for(int i = 0 ; i < 8 ; i ++){
a[i] = a[i] * b[i];
}
fft(a,8,-1);
for(int i = 0 ; i < 8 ; i ++){
cout << i << " " << a[i].x << endl;;
}*/
while(scanf("%s%s",s,t) == )
{
int n = strlen(s), m = strlen(t);
for(int i=;i<n;i++) a[i] = Complex(s[n-i-]-'', );
for(int i=;i<m;i++) b[i] = Complex(t[m-i-]-'', );
int len = n+m-;
int LIM = ;
while(LIM < len) LIM <<= ;
for(int i=n;i<LIM;i++) a[i] = Complex(, );
for(int i=m;i<LIM;i++) b[i] = Complex(, );
fft(a, LIM, );
fft(b, LIM, );
for(int i=;i<LIM;i++) a[i] = a[i] * b[i];
fft(a, LIM, -);
memset(c, , sizeof c);
for(int i=;i<len-;i++)
{
c[i] += (int)(a[i].x + 0.1);
c[i+] += c[i] / ;
c[i] %= ;
}
c[len-] += (int)(a[len-].x + 0.1);
if(c[len-] > )
{
c[len] = c[len-] / ;
c[len-] %= ;
len++;
}
for(int i=len-;i>;i--) if(c[i] == ) len--; else break; // 0 * 345 = 0 instead of 000
for(int i=;i<len/;i++) swap(c[i], c[len-i-]);
for(int i=;i<len;i++) printf("%d",c[i]);
puts("");
}
return ;
}

最新文章

  1. day5
  2. 【练习】数据移动---导入(IMPDP)
  3. [C++] socket -7 [邮槽]
  4. 初探接口测试框架--python系列5
  5. windows下部署 ISCSI存储
  6. 贪心-poj-2437-Muddy roads
  7. InnoDB关键特性之doublewrite
  8. 【Java】对服务器程序的理解
  9. svg text文字居中
  10. xml drawable
  11. windows 开机自动登录,或者说是开机后自动进入桌面
  12. Android官方技术文档翻译——Gradle 插件用户指南(4)
  13. 鸟哥的Linux私房菜笔记第四章
  14. 打包错误--Error:A problem was found with the configuration of task &#39;:app:packageRelease&#39;.
  15. CentOS查找目录或文件
  16. MySQL视图小例子
  17. Vue.js Failed to resolve filter: key
  18. 转:HTML5中的element.dataset
  19. Logstash之三:命令行中常用的命令
  20. SQLyog客户端无法连接MySQL服务器

热门文章

  1. 关于Windows下的访问控制模型
  2. Apollo 与 .net core
  3. js入门之DOM动态创建数据
  4. iOS CGContextRef/UIBezierPath(绘图)
  5. flutter常见编译运行等奇怪问题的汇总汇(l转)
  6. 6.JUC之ReentrantReadWriteLock
  7. Java原子操作类汇总(2)
  8. JAVA笔记整理(七),JAVA几个关键字
  9. PAT1025
  10. 算法102----360笔试(m进制不进位相加最大值)