loj 108 多项式乘法

loj 108 多项式乘法

​​ 题目描述

这是一道模板题。

输入两个多项式，输出这两个多项式的乘积。

输入格式

第一行两个整数 n n n 和 m m m，分别表示两个多项式的次数。

第二行 n+1 n + 1 n+1 个整数，分别表示第一个多项式的 0 0 0 到 n n n 次项前的系数。

第三行 m+1 m + 1 m+1 个整数，分别表示第二个多项式的 0 0 0 到 m m m 次项前的系数。

输出格式

一行 n+m+1 n + m + 1 n+m+1 个整数，分别表示乘起来后的多项式的 0 0 0 到 n+m n + m n+m 次项前的系数。

样例

样例输入

1 2 1 2 1 2 1 样例输出

1 4 5 2 模板

ntt

#include#include#include#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if(T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if(ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=1e5+10;const int g=3;const int mod=998244353;inline int ksm(ll b,int t){static ll tmp; for (tmp=1;t;b=b*b%mod,t>>=1) if (t&1) tmp=tmp*b%mod;return tmp;}int a[N<<2],b[N<<2],R[N<<2],n,m;ll invn;inline int inc(int x,int v){return x+v>=mod?x+v-mod:x+v;}inline int dec(int x,int v){return x-v<0?x-v+mod:x-v;}inline void ntt(int *x,int f){ for (int i=0;i>1]>>1|(i&1)<

fft

#include#include#include#include#define pi acos(-1)using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if(T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if(ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=1e5+10;struct C{ double r,i; inline friend C operator+(const C &a,const C &b){return (C){a.r+b.r,a.i+b.i};} inline friend C operator-(const C &a,const C &b){return (C){a.r-b.r,a.i-b.i};} inline friend C operator*(const C &a,const C &b){return (C){a.r*b.r-a.i*b.i,a.r*b.i+a.i*b.r};} inline void operator*=(const C &a){*this=*this*a;}}a[N<<2],b[N<<2];int n,m,R[N<<2]; inline void fft(C *x,int f){ for (int i=0;i>1]>>1)|(i&1)<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。