题目链接
转 prufer 序，有结论 \(deg _ i - 1 = i\) 在 prufer 序中出现次数。
设一个点的 EGF 为 \(F (x) = \sum _ {n = 0} f _ n \frac {x ^ n} {n!}\)，其中 \(f _ n\) 表示 \(n + 1\) 是否在 \(S\) 内出现过。答案即为 \([\frac {x ^ {n - 2}} {(n - 2)!}] F ^ n (x)\)。
时间复杂度 \(\text O (n \log n)\)。
#include<cstdio>
#include<vector>
using namespace std;const int mod=998244353;
namespace Poly {// ...
} using namespace Poly;
int n,k;
int main() {scanf("%d%d",&n,&k);poly inv(n),fac(n),ifac(n),f(n);inv[1]=fac[0]=ifac[0]=1;for(int i=2;i<n;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;for(int i=1;i<n;i++)fac[i]=1ll*fac[i-1]*i%mod,ifac[i]=1ll*ifac[i-1]*inv[i]%mod;for(int i=1,x;i<=k;i++) scanf("%d",&x),f[x-1]=ifac[x-1];poly g=f^n;printf("%d\n",1ll*g[n-2]*fac[n-2]%mod);return 0;
}