题意:对于k = 0 ... n求

解:

首先把i变成从0开始

我们发现a和b的次数(下标)是成正比例的,这不可,于是反转就行了。

反转b的话,会发现次数和是n + k,这不可。

反转a就很吼了。

这个东西恰好是卷积出来的第n - k项的系数。

所以我们把a串反转,然后用a与b卷积,最后再反转输出即可。

 /**************************************************************
Problem: 2194
Language: C++
Result: Accepted
Time:133643896 ms
Memory:14342474884 kb
****************************************************************/ #include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring> const int N = ;
const double pi = 3.1415926535897932384626; struct cp {
double x, y;
cp(double X = , double Y = ) {
x = X;
y = Y;
}
inline cp operator +(const cp &w) const {
return cp(x + w.x, y + w.y);
}
inline cp operator -(const cp &w) const {
return cp(x - w.x, y - w.y);
}
inline cp operator *(const cp &w) const {
return cp(x * w.x - y * w.y, x * w.y + y * w.x);
}
}a[N << ], b[N << ]; int r[N << ]; inline void FFT(int n, cp *a, int f) {
for(int i = ; i < n; i++) {
if(i < r[i]) {
std::swap(a[i], a[r[i]]);
}
} for(int len = ; len < n; len <<= ) {
cp Wn(cos(pi / len), f * sin(pi / len));
for(int i = ; i < n; i += (len << )) {
cp w(, );
for(int j = ; j < len; j++) {
cp t = a[i + len + j] * w;
a[i + len + j] = a[i + j] - t;
a[i + j] = a[i + j] + t;
w = w * Wn;
}
}
} if(f == -) {
for(int i = ; i <= n; i++) {
a[i].x /= n;
}
}
return;
} int main() {
int n;
scanf("%d", &n);
n--;
for(int i = ; i <= n; i++) {
scanf("%lf%lf", &a[n - i].x, &b[i].x);
} int len = , lm = ;
while(len <= (n << )) {
len <<= ;
lm++;
}
for(int i = ; i <= len; i++) {
r[i] = (r[i >> ] >> ) | ((i & ) << (lm - ));
} FFT(len, a, );
FFT(len, b, );
for(int i = ; i <= len; i++) {
a[i] = a[i] * b[i];
}
FFT(len, a, -); for(int i = ; i <= n; i++) {
printf("%d\n", (int)(a[n - i].x + 0.5));
} return ;
}

AC代码

最新文章

  1. Python ORM Storm 源码修改
  2. 习题-第5章Web自动化测试
  3. easyui datagrid去掉加载提示
  4. Saiku操作界面的简化
  5. 嵌入式 详解udev
  6. phpMyAdmin导入本地数据库
  7. 最大公约数与欧几里得(Euclid)算法
  8. Robotium 不能同时跑多个case
  9. sendmsg: no buffer space available
  10. Js获取元素样式值(getComputedStyle&amp;currentStyle)兼容性解决方案
  11. [POJ] 3468 A Simple Problem with Integers [线段树区间更新求和]
  12. mediawiki在windows下的安装
  13. 关于Android平台的搭建的心得---汪永骏
  14. CF518D. Ilya and Escalator [概率DP]
  15. scrapy的命令行
  16. CDI services--Decorators(装饰器)
  17. PHP APP端微信支付
  18. [No0000163]卷福、神秘博士和一群老戏骨表演群口相声:To be or not to be该咋念,简直高潮迭起
  19. 说一下acad的bug及问题
  20. 解析eml文件

热门文章

  1. spring后置处理器BeanPostProcessor
  2. spring初始化bean时执行某些方法完成特定的初始化操作
  3. sass变量引入全局
  4. 腾讯机试题 AcWing 603 打怪兽
  5. python 钉钉机器人发送消息
  6. how to build an app with github
  7. matlab颜色映射colormap() pcolor()
  8. Codeforces#543 div2 A. Technogoblet of Fire(阅读理解)
  9. Vmware 给虚拟机传脚本并执行
  10. UESTC1013-我的魔法栈-模拟/排列组合