```cpp
/*
Polynomial Template 多项式模板
By: NaCly_Fish
目前支持操作:
poly F; 定义一个多项式F
void print_poly(poly f) 从低到高次输出多项式f的系数
poly multiply(poly f,poly g) 计算多项式f和g的卷积 (多项式乘法)
poly inverse(poly f) 求多项式f的逆
poly integral(poly f) 求多项式f的不定积分(常数项为0)
poly derivative(poly f) 求多项式f的导数
poly logarithm(poly f) 求多项式f的对数
poly devide(poly f,poly g) 求多项式f除以g
poly mod(poly f,poly g,poly q) 在求f除以g之后,以q作为结果,再算出余数
void reverse(poly &f) 翻转多项式f的系数
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define ll long long
#define N 400003
#define reg register
#define p 998244353
using namespace std;
struct poly{
int t;
int a[N];
};
int rev[N],invv[N];
poly F,G,Q,R;
inline void read(int &x);
void print(int x);
inline int power(int a,int t);
void NTT(poly &f,int type,int lim);
inline void qwqqq(poly f,poly g,poly &res,int lim);
inline void print_poly(poly f);
void reverse(poly &f);
poly multiply(poly f,poly g);
poly inverse(poly f);
poly logarithm(poly f);
poly integral(poly f);
poly derivative(poly f);
poly exponential(poly f);
poly add(poly f,poly g);
poly subtract(poly f,poly g);
poly devide(poly f,poly g);
poly mod(poly f,poly g,poly q);
signed main(){
int n,m;
read(n),read(m);
for(int i=0;i<=n;++i) read(F.a[i]);
for(int i=0;i<=m;++i) read(G.a[i]);
F.t = n,G.t = m;
Q = devide(F,G);
R = mod(F,G,Q);
print_poly(Q);
print_poly(R);
return 0;
}
poly mod(poly f,poly g,poly q){
poly res;
int n = f.t,m = g.t;
f.t = m;
q.t = min(q.t,m);
for(reg int i=m+1;i<=(n<<1);++i) f.a[i] = g.a[i] = 0;
for(reg int i=q.t+1;i<=(n<<1);++i) q.a[i] = 0;
res = subtract(f,multiply(q,g));
res.t = m-1;
for(reg int i=m;i<=(n<<1);++i) res.a[i] = 0;
return res;
}
poly devide(poly f,poly g){
poly q;
int n = f.t,m = g.t;
reverse(f),reverse(g);
g.t = f.t = n-m+1;
for(int i=n-m+2;i<=n;++i)
f.a[i] = g.a[i] = 0;
q = multiply(f,inverse(g));
q.t = n-m;
reverse(q);
return q;
}
poly subtract(poly f,poly g){
int l = max(f.t,g.t);
for(reg int i=0;i<=l;++i)
f.a[i] = (f.a[i]-g.a[i]+p)%p;
return f;
}
poly add(poly f,poly g){
int l = max(f.t,g.t);
for(reg int i=0;i<=l;++i)
f.a[i] = (f.a[i]+g.a[i])%p;
return f;
}
void reverse(poly &f){
int l = f.t>>1;
for(reg int i=0;i<=l;++i)
swap(f.a[i],f.a[f.t-i]);
}
poly logarithm(poly f){
int m = f.t;
f = multiply(derivative(f),inverse(f));
f.t = m;
return integral(f);
}
poly integral(poly f){
invv[1] = 1;
++f.t;
for(int i=2;i<=f.t;++i)
invv[i] = (ll)(p-p/i)*invv[p%i]%p;
for(reg int i=f.t;i>=1;--i)
f.a[i] = (ll)f.a[i-1]*invv[i]%p;
f.a[0] = 0;
--f.t;
return f;
}
poly derivative(poly f){
for(reg int i=0;i<f.t;++i)
f.a[i] = (ll)f.a[i+1]*(i+1)%p;
return f;
}
poly inverse(poly f){
int cur = 0,base,l,lim,n;
base = l = 1;
lim = 2;
n = f.t;
poly g[2];
g[cur].a[0] = power(f.a[0],p-2);
for(int i=1;i<=lim;++i)
rev[i] = (rev[i>>1]>>1)|((i&1)<<(l-1));
while(base<=(n<<1)){
cur ^= 1;
memset(g[cur].a,0,sizeof(g[cur].a));
for(reg int i=0;i<base;++i)
g[cur].a[i] = (g[cur^1].a[i]<<1)%p;
cur ^= 1;
qwqqq(g[cur],g[cur],g[cur],lim);
qwqqq(g[cur],f,g[cur],lim);
cur ^= 1;
for(int i=0;i<base;++i)
g[cur].a[i] = (g[cur].a[i]-g[cur^1].a[i]+p)%p;
base <<= 1,lim <<= 1;
++l;
if(base>(n<<1)) continue;
for(int i=1;i<=lim;++i)
rev[i] = (rev[i>>1]>>1)|((i&1)<<(l-1));
}
g[cur].t = n;
return g[cur];
}
inline void qwqqq(poly f,poly g,poly &res,int lim){
poly F,G;
memset(F.a,0,sizeof(F.a));
memset(G.a,0,sizeof(G.a));
for(int i=0;i<=(lim>>1);++i){
F.a[i] = f.a[i];
G.a[i] = g.a[i];
}
NTT(F,1,lim),NTT(G,1,lim);
for(int i=0;i<=lim;++i)
F.a[i] = (ll)F.a[i]*G.a[i]%p;
NTT(F,-1,lim);
int inv = power(lim,p-2);
for(int i=0;i<=lim;++i)
res.a[i] = (ll)F.a[i]*inv%p;
}
inline void print_poly(poly f){
for(int i=0;i<=f.t;++i){
print(f.a[i]);
putchar(' ');
}
putchar('\n');
}
poly multiply(poly f,poly g){
int n = f.t,m = g.t;
int inv,lim = 1,l = 0;
while(lim<=n+m){
lim <<= 1;
++l;
}
--l;
for(int i=1;i<=lim;++i)
rev[i] = (rev[i>>1]>>1)|((i&1)<<l);
NTT(f,1,lim),NTT(g,1,lim);
for(int i=0;i<=lim;++i)
f.a[i] = (ll)f.a[i]*g.a[i]%p;
NTT(f,-1,lim);
inv = power(lim,p-2);
for(int i=0;i<=lim;++i)
f.a[i] = (ll)f.a[i]*inv%p;
f.t = n+m;
return f;
}
void NTT(poly &f,int type,int lim){
for(int i=0;i<=lim;++i){
if(i>=rev[i]) continue;
swap(f.a[i],f.a[rev[i]]);
}
for(int mid=1;mid<lim;mid<<=1){
int rt = power(3,(p-1)/(mid<<1));
if(type==-1) rt = power(rt,p-2);
int r = mid<<1;
for(int j=0;j<lim;j+=r){
int w = 1;
for(int k=0;k<mid;++k){
int x = f.a[j+k];
int y = (ll)w*f.a[j+k+mid]%p;
f.a[j+k] = (x+y)%p;
f.a[j+k+mid] = ((x-y)%p+p)%p;
w = (ll)w*rt%p;
}
}
}
}
inline int power(int a,int t){
int res = 1;
while(t){
if(t&1) res = (ll)res*a%p;
a = (ll)a*a%p;
t >>= 1;
}
return res;
}
inline void read(int &x){
x = 0;
char c = getchar();
while(c<'0'||c>'9') c = getchar();
while(c>='0'&&c<='9'){
x = (x<<3)+(x<<1)+(c^48);
c = getchar();
}
}
void print(int x){
if(x>9) print(x/10);
putchar(x%10+'0');
}
```
by NaCly_Fish @ 2019-03-12 22:24:04
Orz N_F ddjxd
by Le_temps_des_fleurs @ 2019-03-12 22:24:58
@[Neptune_Disaster](/space/show?uid=108185) qaq
by NaCly_Fish @ 2019-03-12 22:25:48
Orz N_F ddjxd
by tiger0133 @ 2019-03-12 22:26:20
qwq
by Le_temps_des_fleurs @ 2019-03-12 22:26:53
@[NaCly_Fish](/space/show?uid=115864) %%%
by yzhang @ 2019-03-12 22:29:18
神仙代码，看不懂
by officeyutong @ 2019-03-12 22:32:18
枫姐姐tqlorz%%%
by VenusM1nT @ 2019-03-12 22:35:50
orz 神仙ljf
by Qingyu @ 2019-03-12 22:36:50
@[NaCly_Fish](/user/115864) Poly结构体作为形参和返回值难道不会爆吗QwQ
by Haishu @ 2020-01-28 13:07:54