UOJ 34 多项式乘法(FFT 快速傅里叶变换 模板)

UOJ 34 多项式乘法

这是一道模板题。

给你两个多项式,请输出乘起来后的多项式。

输入格式

第一行两个整数 nn 和 mm ,分别表示两个多项式的次数。

第二行 n+1n+1 个整数,表示第一个多项式的 00 到 nn 次项系数。

第三行 m+1m+1 个整数,表示第二个多项式的 00 到 mm 次项系数。

输出格式

一行 n+m+1n+m+1 个整数,表示乘起来后的多项式的 00 到 n+mn+m 次项系数。

样例一

input

1 2
1 2
1 2 1

output

1 4 5 2

explanation

(1+2x)⋅(1+2x+x2)=1+4x+5x2+2x3(1+2x)⋅(1+2x+x2)=1+4x+5x2+2x3 。

限制与约定

0≤n,m≤1050≤n,m≤105 ,保证输入中的系数大于等于 00 且小于等于 99 。

时间限制:1s1s

空间限制:256MB

 

最最最最最最最原始的板子

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <complex>
#include <iostream>
using namespace std;

typedef complex<double> cd;     ///复数类的定义
const int maxx = 2094153;       ///nlongn的最大长度
const double pi = acos(-1.0);   ///圆周率

cd ar[maxx], br[maxx];          ///存储中间转换结果
int rev[maxx];                  ///存储二进制反转结果

///二进制转换位置,bit为最长的长度,必定是2的幂
void getrev (int bit)
{
    for (int i = 0; i < (1<<bit); i++)
    {
        rev[i] = (rev[i>>1]>>1)|((i&1)<<(bit-1));
    }
}

///a为转换后的数组,n是数组长度,dft是控制dft和idft
void fft (cd *a, int n, int dft)
{
    ///按照二进制翻转
    for (int i = 0; i < n; i++)
    {
        if (i < rev[i])
        {
            swap(a[i], a[rev[i]]);
        }
    }
    ///蝴蝶操作模拟合并过程
    for (int step = 1; step < n; step <<= 1)        ///模拟合并的次数
    {
        cd wn = exp(cd(0, dft*pi/step));            ///计算单位复根
        for (int j = 0; j < n; j += (step<<1))      ///模拟合并一次的组数
        {
            cd wnk(1, 0);                           ///每个独立序列都是从0开始的
            for (int k = j; k < j+step; k++)        ///模拟合并的每一组
            {
                cd x = a[k];
                cd y = wnk*a[k+step];
                a[k] = x+y;
                a[k+step] = x-y;
                wnk *= wn;                          ///计算下一次复根
            }
        }
    }
    ///idft的情况
    if (dft == -1)
    {
        for (int i = 0; i < n; i++)
        {
            a[i] /= 1.0*n;
        }
    }
}

int output[maxx];           ///输出
int l1,l2;

int main ()
{
    while(scanf("%d%d", &l1, &l2)!=EOF)///两个多项式的次数
    {
        memset(ar,0,sizeof(ar));
        memset(br,0,sizeof(br));
        memset(rev,0,sizeof(rev));
        memset(output,0,sizeof(output));
        l1++;
        l2++;
        for(int i=0; i<l1; i++)///从0到最高项
        {
            scanf("%lf",&ar[i]);
        }
        for(int i=0; i<l2; i++)///从0到最高项
        {
            scanf("%lf",&br[i]);
        }
        int bit = 1, s = 2;     ///bit表示数组的二进制位数,s表示分割的长度
        for (bit = 1; (1<<bit) < l1+l2-1; bit++)
        {
            s <<= 1;            ///找到一个2的整数次幂可以容纳这两个串的乘积
        }
        ///转换数组模拟
        getrev(bit);
        ///分别DFT
        fft(ar, s, 1);
        fft(br, s, 1);
        ///对应相乘
        for (int i = 0; i < s; i++)
        {
            ar[i] *= br[i];
        }
        ///进行IDFT
        fft(ar, s, -1);
        ///存入输出数组
        for (int i = 0; i < s; i++)
        {
            output[i] += (int)(ar[i].real()+0.5);
        }
        for (int i=0; i < l1+l2-1; i++)///从0到最高项的系数
        {
            if(i)
                cout<<' ';
            printf("%d", output[i]);
        }
        cout<<'\n';
    }
    return 0;
}

 

 

 

 

 

 

 

 

全部评论

相关推荐

避坑恶心到我了大家好,今天我想跟大家聊聊我在成都千子成智能科技有限公司(以下简称千子成)的求职经历,希望能给大家一些参考。千子成的母公司是“同创主悦”,主要经营各种产品,比如菜刀、POS机、电话卡等等。听起来是不是有点像地推销售公司?没错,就是那种类型的公司。我当时刚毕业,急需一份临时工作,所以在BOSS上看到了千子成的招聘信息。他们承诺无责底薪5000元,还包住宿,这吸引了我。面试的时候,HR也说了同样的话,感觉挺靠谱的。于是,我满怀期待地等待结果。结果出来后,我通过了面试,第二天就收到了试岗通知。试岗的内容就是地推销售,公司划定一个区域,然后你就得见人就问,问店铺、问路人,一直问到他们有意向为止。如果他们有兴趣,你就得摇同事帮忙推动,促进成交。说说一天的工作安排吧。工作时间是从早上8:30到晚上18:30。早上7点有人叫你起床,收拾后去公司,然后唱歌跳舞(销售公司都这样),7:55早课(类似宣誓),8:05同事间联系销售话术,8:15分享销售技巧,8:30经理训话。9:20左右从公司下市场,公交、地铁、自行车自费。到了市场大概10点左右,开始地推工作。中午吃饭时间大约是12:00,公司附近的路边盖饭面馆店自费AA,吃饭时间大约40分钟左右。吃完饭后继续地推工作,没有所谓的固定中午午休时间。下午6点下班后返回公司,不能直接下班,需要与同事交流话术,经理讲话洗脑。正常情况下9点下班。整个上班的一天中,早上到公司就是站着的,到晚上下班前都是站着。每天步数2万步以上。公司员工没有自己的工位,百来号人挤在一个20平方米的空间里听经理洗脑。白天就在市场上奔波,公司的投入成本几乎只有租金和工资,没有中央空调。早上2小时,晚上加班2小时,纯蒸桑拿。没有任何福利,节假日也没有3倍工资之类的。偶尔会有冲的酸梅汤和西瓜什么的。公司的晋升路径也很有意思:新人—组长—领队—主管—副经理—经理。要求是业绩和团队人数,类似传销模式,把人留下来。新人不能加微信、不能吐槽公司、不能有负面情绪、不能谈恋爱、不能说累。在公司没有任何坐的地方,不能依墙而坐。早上吃早饭在公司外面的安全通道,未到上班时间还会让你吃快些不能磨蹭。总之就是想榨干你。复试的时候,带你的师傅会给你营造一个钱多事少离家近的工作氛围,吹嘘工资有多高、还能吹自己毕业于好大学。然后让你早点来公司、无偿加班、抓住你可能不会走的心思进一步压榨你。总之,大家在找工作的时候一定要擦亮眼睛,避免踩坑!———来自网友
qq乃乃好喝到咩噗茶:不要做没有专业门槛的工作
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务