Solution

简单式子 + 毒瘤经典问题

常数巨大无比？？

https://zhuanlan.zhihu.com/p/51279047

在分治求积的过程中耗费了大量时间。

Code

// Code by ajcxsu
// Problem: vanyousee

#include<bits/stdc++.h>
#define MOD (998244353)
using namespace std;

typedef int _int;
const int N=4e5+10, M=1e5+10;
int a[N], b[N], ca[N], cb[N], f[N], g[N], f2[N], g2[N], nt[N];
int fac[N], finv[N];
int r[N], n;
void gen(int m) {
    int l=0; for(n=1; n<=m; n<<=1) l++;
    for(int i=1; i<n; i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
}
int qpow(int x, int y) {
    int ret=1;
    while(y) {
        if(y&1) ret=1ll*ret*x%MOD;
        x=1ll*x*x%MOD, y>>=1;
    }
    return ret;
}
void dft(int x[], int d) {
    int t, w, o;
    for(int i=1; i<n; i++) if(i>r[i]) swap(x[i], x[r[i]]);
    for(int i=1; i<n; i<<=1) {
        o=qpow(3, d*(MOD-1)/(i<<1)+MOD-1);
        for(int j=0; j<n; j+=(i<<1)) {
            w=1;
            for(int k=0; k<i; k++, w=1ll*w*o%MOD)
                t=1ll*x[i+j+k]*w%MOD, x[i+j+k]=(x[j+k]-t+MOD)%MOD,
                (x[j+k]+=t)%=MOD;
        }
    }
}
int ta[N], tb[N];
void mul(int x[], int y[], int z[], int m, int mode=0) {
    gen(m<<1);
    copy(x, x+m, ta), copy(y, y+m, tb);
    fill(ta+m, ta+n, 0), fill(tb+m, tb+n, 0);
    dft(ta, 1), dft(tb, 1);
    for(int i=0; i<n; i++)
        if(!mode) ta[i]=1ll*ta[i]*tb[i]%MOD;
        else ta[i]=(2ll*tb[i]-1ll*ta[i]*tb[i]%MOD*tb[i]%MOD+MOD)%MOD;
    dft(ta, -1); int inv=qpow(n, MOD-2); for(int i=0; i<m; i++) z[i]=1ll*ta[i]*inv%MOD;
}

int L[21][M], R[21][M];
void dfs(int x[], int y[], int l, int r, int dep=0) {
    if(l==r) { y[0]=1, y[1]=x[l]; return; }
    int mid=(l+r)>>1, *L=::L[dep], *R=::R[dep];
    fill(L, L+r-l+4, 0), fill(R, R+r-l+4, 0);
    dfs(x, L, l, mid, dep+1), dfs(x, R, mid+1, r, dep+1);
    mul(L, R, y, (r-l+2)+2);
}

void polyinv(int x[], int y[], int deg) {
    if(deg==1) { y[0]=qpow(x[0], MOD-2); return; }
    polyinv(x, y, (deg+1)>>1);
    mul(x, y, y, deg, 1);
}
void deri(int x[], int n) {
    for(int i=0; i<n; i++) x[i]=1ll*(i+1)*x[i+1]%MOD;
    x[n-1]=0;
}
void inte(int x[], int n) {
    for(int i=n-1; i; i--) x[i]=1ll*qpow(i, MOD-2)*x[i-1]%MOD;
    x[0]=0;
}
void polyln(int x[], int y[], int deg) {
    int a[N]={0}; polyinv(x, a, deg), copy(x, x+deg, y);
    deri(y, deg);
    mul(y, a, y, deg);
    inte(y, deg);
}

int p[]={-1, 1};
template<typename T> inline void gn(T &x) {
    char ch=getchar(); x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar(); 
}
_int main() {
    fac[0]=fac[1]=finv[0]=finv[1]=1;
    for(int i=2; i<N; i++) fac[i]=1ll*fac[i-1]*i%MOD, finv[i]=MOD-1ll*MOD/i*finv[MOD%i]%MOD;
    for(int i=2; i<N; i++) finv[i]=1ll*finv[i]*finv[i-1]%MOD;
    int n, m; gn(n), gn(m);
    for(int i=1; i<=n; i++) gn(a[i]);
    for(int j=1; j<=m; j++) gn(b[j]);
    int t;
    gn(t);
    dfs(a, f2, 1, n), dfs(b, g2, 1, m);
    polyln(f2, f, t+1), polyln(g2, g, t+1);
    for(int i=1; i<=t; i++)
        f[i]=(MOD+1ll*p[i&1]*f[i]*finv[i-1]%MOD)%MOD, 
        g[i]=(MOD+1ll*p[i&1]*g[i]*finv[i-1]%MOD)%MOD;
    f[0]=n, g[0]=m;
    mul(f, g, f, t+1);
    int inv=qpow(1ll*n*m%MOD, MOD-2);
    for(int i=1; i<=t; i++) printf("%lld\n", 1ll*fac[i]*f[i]%MOD*inv%MOD);
    return 0;
}