题解 P6062 【燔祭 sacrificial】
_QAQ
2020-02-03 22:42:55
前置知识:拉格朗日插值
给一个不用 $\operatorname{prufer}$ 序列的做法。
首先求给定一棵树赋权的方法,以 $f_{i,j}$ 表示第 $i$ 个节点赋值为 $j$ 的方案,那么有
$$
f_{i,j}=\prod_{(i,x) \in E,x ≠fa_i}\sum_{i=1}^j f_{x,i}
$$
容易发现 $f_{i,j}$ 可以看做关于 $j$ 的至多 $n+1$ 次多项式,以 $F_i(j)$ 表示,所以只要求出根节点赋权 $[1,m+1]$ 的方案,再拉格朗日插值即可。
考虑如何计算 $n$ 个节点,根节点赋权为 $i,i \in [1,m+1]$ 的方法,考虑对于一个节点 $x$,若其有 $k$ 个孩子,其赋权方式以及树的结构均相同,那么显然方案中有系数 $\frac{1}{k!}$。
考虑在已知 $f_{i,x},x \in [1,j)$ 的情况下,枚举计算 $f_{i,j}$。
有
$$
f_{i,j}=[x^j] \prod_{c=1}^{j-1} e^{cx \times f_{i,c}}
$$
考虑暴力计算,复杂度为 $O(n^4 \log n)$,无法接受。
但发现该式中,$i$ 相同的情况下,$f_{i,j}$ 到 $f_{i,j+1}$ 的多项式中本质上只少了一个 $e^{xj \times f_{i,j}}$,其系数在 $[0,n]$ 中有意义项只有 $\frac{n}{j}$ 个,所以复杂度为
$$
n^2\sum_{i=1}^n \frac{n}{i}=n^3\ln n
$$
最后不要忘了乘上 $n!$。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=4e3+7,p=998244353; long long v;
int n,m,r[N],w[N],fac[N],f[N][N]; long long g[N];
inline long long pows(long long u,int v){
long long ans=1; while(v>0) {if(v&1) ans=ans*u%p; u=u*u%p,v=v>>1;} return ans;
}
int main(){
cin>>n>>m,f[1][1]=1,r[0]=1,fac[0]=1;
for(int i=1;i<=n;i++) r[i]=r[i-1]*pows(i,p-2)%p,fac[i]=pows(r[i],p-2);
for(int i=1;i<=n+3;i++){
f[1][i]=i,g[0]=1;
for(int x=1;x<=n;x++) g[x]=pows(i,x)*r[x]%p;
for(int x=2;x<=n;x++){
f[x][i]=g[x-1];
if(f[x][i]+f[x][i-1]>=p) f[x][i]=f[x][i]+f[x][i-1]-p;
else f[x][i]=f[x][i]+f[x][i-1];
for(int c=1;c*x<=n;c++) w[c]=pows(f[x][i],c)*r[c]%p;
for(int c=n;c>=x;c--)
for(int t=1;t*x<=c;t++)
g[c]=(g[c]+g[c-t*x]*w[t])%p;
}
}
v=1; long long op=0;
for(int i=1;i<=n;i++) v=1ll*v*i%p;
if(m<=n+3) op=f[n][m];
else{
for(int i=1;i<=n+3;i++){
long long val=f[n][i];
for(int j=1;j<=n+3;j++){
if(i==j) continue;
val=val*(m-j)%p*pows(i-j,p-2)%p;
}
op=(op+val)%p;
}
}
cout<<(op+p)*v%p<<endl;
return 0;
}
```