[atAGC106F]Figures

考虑purfer序列，若生成树的pufer序列为$p_{i}$，则答案为$(\prod_{i=1}^{n}a_{i})\sum_{p}\prod_{i=1}^{n}\frac{(a_{i}-1)!}{(a_{i}-1-s_{i})!}$（其中$s_{i}$为$p$中点$i$出现的次数，即度数减1）

（以下令$a_{i}$减1）观察到式子只与$s_{i}$有关，对于相同的$s_{i}$对应$p_{i}$有$\frac{(n-2)!}{\prod_{i=1}^{n}s_{i}!}$种，令$C=(n-2)!\prod_{i=1}^{n}a_{i}$，代入即$ans=C\sum_{\sum_{i=1}^{n}s_{i}=n-2}\prod_{i=1}^{n}\frac{a_{i}!}{s_{i}!(a_{i}-s_{i})!}$

令$f(x)=\sum_{k=0}^{n-2}(\sum_{\sum_{i=1}^{n}s_{i}=k}\frac{a_{i}!}{s_{i}!(a_{i}-s_{i})!})x^{k}=\sum_{s_{i}}\prod_{i=1}^{n}\frac{a_{i}!}{s_{i}!(a_{i}-s_{i})!}\cdot x^{s_{i}}$，答案即$f(x)[x^{n-2}]$

不妨先枚举$s_{1},s_{2},..$，再提取出对应位置上的式子作为公因式，之后由于各位上完全独立，再将结果乘起来就是原式，即$f(x)=\prod_{i=1}^{n}\sum_{s_{i}=0}^{a_{i}}\frac{a_{i}!}{s_{i}!(a_{i}-s_{i})!}\cdot x^{s_{i}}=(1+x)^{\sum_{i=1}^{n}a_{i}}$

因此$f(x)[x^{n-2}]=c(\sum_{i=1}^{n}a_{i},n-2)$（注意这里的$a_{i}$减了1），发现$(n-2)!$已经被抵消掉，因此直接枚举$\sum_{i=1}^{n}a_{i}$到$\sum_{i=1}^{n}a_{i}-(n-2)+1$即可

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define mod 998244353

 4 int n,x,s,ans;

 5 int main(){

 6     scanf("%d",&n);

 7     ans=1;

 8     for(int i=1;i<=n;i++){

 9         scanf("%d",&x);

10         ans=1LL*ans*x%mod;

11         s=(s+x-1)%mod;

12     }

13     for(int i=0;i<n-2;i++)ans=1LL*ans*(s-i+mod)%mod;

14     printf("%d",ans);

15 }

巴特西

[atAGC106F]Figures

最新文章

热门文章