题解 P6062 【燔祭 sacrificial】

_QAQ

2020-02-03 22:42:55

Solution

前置知识:拉格朗日插值 给一个不用 $\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; } ```