题目分析

题目地址->here

这是一道二合一题，对于 50% 的数据，有 $\sum n \leq 10^5$，对于 50% 的数据有 $\sum n \leq 2*10^6,K=1$。

显然 prufer 编码，出现 $i$次的点度数为 $i+1$。设 $f(i,j)$表示考虑到第 $i$个点，此时的 prufer 序列长度为 $j$的所有情况度数积的 $K$次方之和。

$$f(t,i)=\sum_{j=0}^i C_i^j (j+1)^Kf(t-1,i-j)$$

写成卷积的形式：

$$\frac{f(t,i)}{i!}=\sum_{j=0}^i \frac{f(t-1,j)}{j!}\frac{(i-j+1)^K}{(i-j)!}$$

设 $A_i=\frac{(i+1)^K}{i!}$，求出 $A(x)^n$的 $n-2$次项即可知道答案，用倍增＋NTT 可以做到 $O(n \log^2 n)$，看 CC 的排行榜上有狼灭老哥用多项式求 exp 和 ln 的方法做到了 $O(n \log n)$，可以过 50% 的数据。

接下来用生成函数做第二问。

$$A(x)=\sum_{i=0} \frac{i+1}{i!}x^i=\sum_{i=0} \frac{1}{(i-1)!}x^i+\sum_{i=0} \frac{1}{i!} x^i=(x+1)e^x$$

$$A(x)^n=(x+1)^ne^{nx}=(\sum_{i=0}^n C_n^ix^i)(\sum_{i=0} \frac{n^i}{i!}x^i)$$

$n-2$次项为 $\sum_{i=0}^{n-2}C_{n}^{i+2}\frac{n^i}{i!}$。

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
const int mod=998244353,N=2000000,KN=2097160;
int T,n,K;
int ifac[N+5],fac[N+5],inv[N+5],bin[N+5];
int A[KN],res[KN],rev[KN];

int qm(int x) {return x>=mod?x-mod:x;}
int qpow(int x,int y) {
    int re=1;
    for(;y;y>>=1,x=1LL*x*x%mod) if(y&1) re=1LL*re*x%mod;
    return re;
}
void work1() {
    int ans=0;
    bin[0]=1;for(RI i=1;i<=n-2;++i) bin[i]=1LL*bin[i-1]*n%mod;
    for(RI i=0;i<=n-2;++i)
        ans=qm(ans+1LL*fac[n]*ifac[i+2]%mod*ifac[n-i-2]%mod*ifac[i]%mod*bin[i]%mod);
    printf("%lld\n",1LL*ans*qpow(bin[n-2],mod-2)%mod*fac[n-2]%mod);
}

void NTT(int *a,int n,int x) {
    for(RI i=0;i<n;++i) if(rev[i]>i) swap(a[i],a[rev[i]]);
    for(RI i=1;i<n;i<<=1) {
        int gn=qpow(3,(mod-1)/(i<<1));
        for(RI j=0;j<n;j+=(i<<1))
            for(RI k=0,g=1;k<i;++k,g=1LL*g*gn%mod) {
                int t1=a[j+k],t2=1LL*g*a[j+i+k]%mod;
                a[j+k]=qm(t1+t2),a[j+i+k]=qm(t1-t2+mod);
            }
    }
    if(x==1) return;
    reverse(a+1,a+n);int invn=qpow(n,mod-2);
    for(RI i=0;i<n;++i) a[i]=1LL*a[i]*invn%mod;
}
void work2() {
    int kn=1,len=0;while(kn<=(n-2)*2) kn<<=1,++len;
    for(RI i=0;i<kn;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(len-1));
    for(RI i=0;i<kn;++i) A[i]=res[i]=0;
    for(RI i=0;i<=n-2;++i) A[i]=1LL*qpow(i+1,K)*ifac[i]%mod;
    res[0]=1,NTT(A,kn,1);
    for(RI i=n;i;i>>=1) {
        if(i&1) {
            NTT(res,kn,1);
            for(RI i=0;i<kn;++i) res[i]=1LL*res[i]*A[i]%mod;
            NTT(res,kn,-1);
            for(RI i=n-1;i<kn;++i) res[i]=0;
        }
        for(RI i=0;i<kn;++i) A[i]=1LL*A[i]*A[i]%mod;
        NTT(A,kn,-1);
        for(RI i=n-1;i<kn;++i) A[i]=0;
        NTT(A,kn,1);
    }
    printf("%lld\n",1LL*res[n-2]*qpow(qpow(n,n-2),mod-2)%mod*fac[n-2]%mod);
}

int main()
{
    scanf("%d",&T);
    fac[0]=1;for(RI i=1;i<=N;++i) fac[i]=1LL*fac[i-1]*i%mod;
    ifac[0]=1,inv[0]=inv[1]=1;
    for(RI i=2;i<=N;++i) inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
    for(RI i=1;i<=N;++i) ifac[i]=1LL*ifac[i-1]*inv[i]%mod;
    while(T--) {
        scanf("%d%d",&n,&K);
        if(K==1) work1();
        else work2();
    }
    return 0;
}