题目概述

Luogu4705

解题报告

二项式展开后：

$$ {t!\over nm}\sum_{k=0}^{t}{1\over k!}(\sum_{i=1}^{n}a_i^k){1\over(t-k)!}(\sum_{j=1}^{m}b_j^{t-k}) $$

现在的问题只有如何快速求出 $F(x)=\sum_{i=0}^{t}(\sum_{j=1}^{n}a_j^i)x^i$ ，得出后就可以卷积求出每个 $t$ 的答案。

令 $f_i(x)=\sum_{k=0}^{t}a_i^kx^k={1\over 1-a_ix}$ ，则 $F(x)=\sum_{i=1}^{n}{1\over 1-a_ix}$ ，这个很不可求。

由于是倒数形式，考虑用 $\ln$ 使其变为非倒数形式，并想办法变为 $\ln$ 的加法式：

$$ [\ln(1-a_ix)]'={-a_i\over 1-a_ix}\\ g_i(x)=-[\ln(1-a_ix)]'={a_i\over 1-a_ix}\\ f_i(x)=xg_i(x)+1\\ F(x)=\sum_{i=1}^{n}xg_i(x)+1=n+x\sum_{i=1}^{n}g_i(x)=n-x\sum_{i=1}^{n}[\ln(1-a_ix)]'\\ [\ln f(x)]'+[\ln g(x)]'={f'(x)\over f(x)}+{g'(x)\over g(x)}=[\ln f(x)g(x)]'\\ F(x)=n-x\{{\ln[\prod_{i=1}^{n}(1-a_ix)]}\}' $$

这样就可以分治NTT+多项式ln求出 $F(x)$ 了。

示例程序

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;typedef vector<int> PN;
const int maxn=100000,maxt=1<<18,MOD=998244353;

int n,m,K,a[maxn+5],b[maxn+5];
int INV[maxt+5],fac[maxt+5],wn[maxt+5],temA[maxt+5],temB[maxt+5];
PN A,B;int H[maxt+5],F[maxt+5],G[maxt+5];

inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;}
inline int MUL(int x,int y) {return (LL)x*y%MOD;}
int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=MUL(w,w)) if (b&1) s=MUL(s,w);return s;}
__attribute__((constructor)) void NTTPre(){
    int x=Pow(3,(MOD-1)/maxt);
    wn[maxt>>1]=1;
    for (int i=(maxt>>1)+1;i<maxt;i++) wn[i]=MUL(wn[i-1],x);
    for (int i=(maxt>>1)-1;i;i--) wn[i]=wn[i<<1];
    INV[0]=INV[1]=1;for (int i=2;i<=maxt;i++) INV[i]=MUL(MOD-MOD/i,INV[MOD%i]);
    fac[0]=1;for (int i=1;i<=maxt;i++) fac[i]=MUL(fac[i-1],i),INV[i]=MUL(INV[i-1],INV[i]);
}
void NTT(int *a,int n,int f){
    if (f>0){
        for (int k=n>>1;k;k>>=1)
            for (int i=0;i<n;i+=k<<1)
                for (int j=0;j<k;j++){
                    int x=a[i+j],y=a[i+j+k];
                    a[i+j+k]=MUL(x+MOD-y,wn[k+j]);
                    a[i+j]=ADD(x,y);
                }
    } else {
        for (int k=1;k<n;k<<=1)
            for (int i=0;i<n;i+=k<<1)
                for (int j=0;j<k;j++){
                    int x=a[i+j],y=MUL(a[i+j+k],wn[k+j]);
                    a[i+j+k]=ADD(x,MOD-y);
                    a[i+j]=ADD(x,y);
                }
        for (int i=0,INV=MOD-(MOD-1)/n;i<n;i++) a[i]=MUL(a[i],INV);
        reverse(a+1,a+n);
    }
}
void Inte(int *F,int *a,int n,int K){
    for (int i=n+K;i>=K;i--) F[i]=MUL(a[i-K],MUL(INV[i],fac[i-K]));
    for (int i=0;i<K;i++) F[i]=0;
}
void Deri(int *F,int *a,int n,int K){
    for (int i=0;i<=n-K;i++) F[i]=MUL(a[i+K],MUL(fac[i+K],INV[i]));
    for (int i=n-K+1;i<=n;i++) F[i]=0;
}
void Inv(int *F,int *a,int n){
    if (n==1) {F[0]=Pow(a[0],MOD-2);return;}
    Inv(F,a,n>>1);
    for (int i=0;i<n;i++) temA[i]=a[i],temA[i+n]=F[i+n]=0;
    NTT(temA,n<<1,1);NTT(F,n<<1,1);
    for (int i=0;i<(n<<1);i++) temA[i]=MUL(F[i],2+MOD-MUL(temA[i],F[i]));
    NTT(temA,n<<1,-1);for (int i=0;i<n;i++) F[i]=temA[i],F[i+n]=0;
}
void Ln(int *F,int *a,int n){
    Inv(temB,a,n);
    Deri(temA,a,n-1,1);for (int i=0;i<n;i++) temA[i+n]=0;
    NTT(temA,n<<1,1);NTT(temB,n<<1,1);
    for (int i=0;i<(n<<1);i++) temA[i]=MUL(temA[i],temB[i]);
    NTT(temA,n<<1,-1);Inte(F,temA,n-2,1);
}
PN operator * (const PN &a,const PN &b){
    static PN c;
    int n=a.size(),m=b.size(),t;
    for (t=1;t<n+m-1;t<<=1);
    for (int i=0;i<n;i++) temA[i]=a[i];for (int i=n;i<t;i++) temA[i]=0;
    for (int i=0;i<m;i++) temB[i]=b[i];for (int i=m;i<t;i++) temB[i]=0;
    NTT(temA,t,1);NTT(temB,t,1);
    for (int i=0;i<t;i++) temA[i]=MUL(temA[i],temB[i]);
    NTT(temA,t,-1);
    c.resize(n+m-1);for (int i=0;i<n+m-1;i++) c[i]=temA[i];
    return c;
}
PN Solve(int *a,int L,int R){
    if (L==R) return {1,(MOD-a[L])%MOD};
    int mid=L+(R-L>>1);
    return Solve(a,L,mid)*Solve(a,mid+1,R);
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<=m;i++) scanf("%d",&b[i]);
    scanf("%d",&K);
    A=Solve(a,1,n);B=Solve(b,1,m);
    int t;for (t=1;t<=K;t<<=1);
    A.resize(t);B.resize(t);
    Ln(H,A.data(),t);Deri(H,H,K,1);
    F[0]=n;for (int i=1;i<=K;i++) F[i]=MUL(MOD-H[i-1],INV[i]);
    Ln(H,B.data(),t);Deri(H,H,K,1);
    G[0]=m;for (int i=1;i<=K;i++) G[i]=MUL(MOD-H[i-1],INV[i]);
    NTT(F,t<<1,1);NTT(G,t<<1,1);
    for (int i=0;i<(t<<1);i++) F[i]=MUL(F[i],G[i]);
    NTT(F,t<<1,-1);
    int INV=Pow(MUL(n,m),MOD-2);
    for (int i=1;i<=K;i++) printf("%d\n",MUL(F[i],MUL(fac[i],INV)));
    return 0;
}