频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
BZOJ2194快速傅立叶之二
2017-01-13 10:30:00         来源:LZJ209的博客  
收藏   我要投稿

BZOJ 2194快速傅立叶之二:这道题体现了快速傅里叶变换最重要的应用:求卷积。所谓卷积根本没有必要去看百度上那晦涩难懂的定义,只要拿多项式联想一下就好了,我们求快速傅里叶变换实际上就是求出了两个多项式相乘之后对应次数未知数的系数。

这就叫做两个多项式的卷积,那么什么样的多项式能用的上卷积呢,就是要求的东西下标相加之后为定值,用FFT求完之后的结果就是每一个定值的系数。就像这道题,虽然i+i-k并不是一个定值,但是如果我们将a数组倒过来,每个i变为n-i的话就会发现原式变为了n-k,这样求出来的卷积第n-k位对应的就是c[k]的值,倒着输出就好了。

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
struct cpx
{
    double a,b;
    cpx(double _=0.0,double __=0.0):a(_),b(__){}
    cpx operator +(cpx x) {return cpx(a+x.a,b+x.b);}
    cpx operator -(cpx x) {return cpx(a-x.a,b-x.b);}
    cpx operator *(cpx x) {return cpx(a*x.a-b*x.b,a*x.b+b*x.a);}
}a[300000],b[300000],c[300000];
const double DFT=2.0;
const double IDFT=-2.0;
double trans_form;
const double pi=acos(-1);
int len;
int pos[300000];
void init()
{
    for(int i=0;i>1]>>1;
        if(i&1) pos[i]|=(len>>1);
    }
}
void trans(cpx x[])
{
    for(int i=0;i>1;
        cpx wm(cos(2*pi/(double)i),sin(trans_form*pi/(double)i));
        for(int j=0;j=0;i--) printf("%d\n",int(c[i].a+0.5));
    return 0;
}
点击复制链接 与好友分享!回本站首页
上一篇:Bellmon_Ford算法详解
下一篇:BZOJ1923外星千足虫(高斯消元)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站