题目分析
题目地址->here
这是一道二合一题，对于 50% 的数据，有 ∑n≤105，对于 50% 的数据有 ∑n≤2∗106,K=1。
显然 prufer 编码，出现 i次的点度数为 i+1。设 f(i,j)表示考虑到第 i个点，此时的 prufer 序列长度为 j的所有情况度数积的 K次方之和。
f(t,i)=i∑j=0Cji(j+1)Kf(t−1,i−j)
写成卷积的形式：
f(t,i)i!=i∑j=0f(t−1,j)j!(i−j+1)K(i−j)!
设 Ai=(i+1)Ki!，求出 A(x)n的 n−2次项即可知道答案，用倍增＋NTT 可以做到 O(nlog2n)，看 CC 的排行榜上有狼灭老哥用多项式求 exp 和 ln 的方法做到了 O(nlogn)，可以过 50% 的数据。
接下来用生成函数做第二问。
A(x)=∑i=0i+1i!xi=∑i=01(i−1)!xi+∑i=01i!xi=(x+1)ex
A(x)n=(x+1)nenx=(n∑i=0Cinxi)(∑i=0nii!xi)
n−2次项为 ∑n−2i=0Ci+2nnii!。
代码
#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;
}
0 条评论