题目描述
给定一个 n 次多项式 F(x) 和一个 m 次多项式 G(x) ，请求出多项式 Q(x), R(x)，满足以下条件：

Q(x) 次数为 n−m，R(x) 次数小于 m
F(x) = Q(x) * G(x) + R(x)
所有的运算在模 998244353 意义下进行。

输入格式
第一行两个整数 n，m，意义如上。
第二行 n+1个整数，从低到高表示 F(x) 的各个系数。
第三行 m+1 个整数，从低到高表示 G(x) 的各个系数。

输出格式
第一行 n−m+1 个整数，从低到高表示 Q(x) 的各个系数。
第二行 m 个整数，从低到高表示 R(x) 的各个系数。
如果 R(x) 不足 m−1 次，多余的项系数补 0。

证明过程见笔记本。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#define ll long long
#define llu unsigned ll
#define int ll
using namespace std;
const int maxn=8e5+100;
const int p=998244353;
const int gg=3;
int fi[maxn];
int f[maxn],g[maxn],q[maxn],r[maxn],c[maxn];
int fr[maxn],gr[maxn],invg[maxn];

int mypow(int a,int b)
{
    if(b<0) return mypow(mypow(a,p-2),-b);
    int ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans%p;
}

void ntt(int *x,int len,int f)
{
    for(int i=0;i<len;i++)
        if(i<fi[i]) swap(x[i],x[fi[i]]);

    for(int i=1;i<len;i<<=1)
    {
        int r=i<<1;
        int wn=mypow(gg,f*(p-1)/r);
        for(int j=0;j<len;j+=r)
        {
            int w=1;
            for(int k=0;k<i;k++)
            {
                int xx=x[j+k],yy=w*x[j+i+k]%p;
                x[j+k]=((xx+yy)%p+p)%p;
                x[j+i+k]=((xx-yy)%p+p)%p;
                w=w*wn%p;
            }
        }
    }
    if(f==-1)
    {
        int invn=mypow(len,p-2);
        for(int i=0;i<len;i++)
            x[i]=x[i]*invn%p;
    }

}

void getntt(int *a,int n,int *b,int m)
{
    int len=1,cnt=0;
    while(len<=(n+m)) len<<=1,cnt++;
    for(int i=0;i<len;i++)
        fi[i]=((fi[i>>1]>>1)|((i&1)<<(cnt-1)));

    ntt(a,len,1);
    ntt(b,len,1);
    for(int i=0;i<len;i++)
        a[i]=a[i]*b[i]%p;
    ntt(a,len,-1);
}

void dfs(int n,int *a,int *b)
{
    if(n==1)
    {
        b[0]=mypow(a[0],p-2);
        return ;
    }
    dfs((n+1)>>1,a,b);
    int len=1,cnt=0;
    while(len<=(n<<1)) len<<=1,cnt++;
    for(int i=0;i<len;i++)
    {
        fi[i]=((fi[i>>1]>>1)|((i&1)<<(cnt-1)));
        c[i]=(i<n?a[i]:0);
    }
    ntt(c,len,1);
    ntt(b,len,1);
    for(int i=0;i<len;i++)
        b[i]=(2-c[i]*b[i]%p+p)%p*b[i]%p;
    ntt(b,len,-1);
    for(int i=n;i<len;i++)
        b[i]=0;
}


signed main(void)
{
    int n,m;
    scanf("%lld%lld",&n,&m);
    for(int i=0;i<=n;i++)
        scanf("%lld",&f[i]),fr[n-i]=f[i];
    for(int i=0;i<=m;i++)
        scanf("%lld",&g[i]),gr[m-i]=g[i];

    for(int i=n-m+1;i<=m;i++)
        gr[i]=0;
    //dfs的第一个参数为多项式项数
    dfs(n-m+1,gr,invg);

    for(int i=0;i<n-m+1;i++)
        q[i]=fr[i];
    getntt(q,n-m,invg,n-m);
    reverse(q,q+n-m+1);
    for(int i=0;i<=n-m;i++)
        printf("%lld ",q[i]),r[i]=q[i];//直接复制给r，要不然q第n-m项以后的还需要清空。
    putchar('\n');

    getntt(g,m,r,n-m);
    for(int i=0;i<m;i++)
        printf("%lld ",(f[i]-g[i]+p)%p);
    putchar('\n');


    return 0;
}