2020-2021:teams:legal_string:jxm2001:contest:arc_106
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:contest:arc_106 [2021/02/15 12:38] jxm2001 |
2020-2021:teams:legal_string:jxm2001:contest:arc_106 [2021/02/15 17:06] (当前版本) jxm2001 [题解] |
||
|---|---|---|---|
| 行 79: | 行 79: | ||
| </hidden> | </hidden> | ||
| + | ===== F - Figures ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定 $n$ 个带标号点，每个点有 $a_i$ 个不同的接口，每个接口最多有一个度，问生成树的个数。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 设每个点度数为 $d_i$，于是在每个生成树中每个点的贡献为 $a_i^{\underline{d_i}}$。根据 $\text{prufer}$ 序列性质，答案为 | ||
| + | |||
| + | $$ | ||
| + | \sum_{\sum d_i=2n-2}\binom{n-2}{d_1-1,d_2-1\cdots d_n-1}\prod_{i=1}^n a_i^{\underline{d_i}}= | ||
| + | \sum_{\sum d_i=2n-2}\frac{(n-2)!}{(d_1-1)!(d_2-1)!\cdots (d_n-1)!}\prod_{i=1}^n a_i^{\underline{d_i}} | ||
| + | $$ | ||
| + | |||
| + | 发现这东西可以用指数型生成函数搞，为方便处理，令 $c_i=d_i+1$，于是上式化为 | ||
| + | |||
| + | $$ | ||
| + | \sum_{\sum c_i=n-2}\binom{n-2}{c_1,c_2\cdots c_n}\prod_{i=1}^n a_i^{\underline{c_i+1}} | ||
| + | $$ | ||
| + | |||
| + | 考虑 $a_i=k$ 的点对应的生成函数，枚举 $c\in [0,k-1]$，贡献为 $k^{\underline{c+1}}$，于是有 | ||
| + | |||
| + | $$ | ||
| + | \begin{equation}\begin{split} | ||
| + | f_k(x)&=\sum_{i=0}^{k-1}\cfrac {k^{\underline{i+1}}}{i!}x^i \\ | ||
| + | &=\sum_{i=0}^{k-1}\cfrac {k!}{i!(k-1-i)!}x^i\\ | ||
| + | & =k(x+1)^{k-1} | ||
| + | \end{split}\end{equation} | ||
| + | $$ | ||
| + | |||
| + | 答案为 | ||
| + | |||
| + | $$ | ||
| + | \begin{equation}\begin{split} | ||
| + | [x^{n-2}](n-2)!\prod_{i=1}^n f_{a_i}(x) &=(n-2)!\prod_{i=1}^n a_i[x^{n-2}](x+1)^{\sum(a_i-1)} \\ | ||
| + | &=(n-2)!\prod_{i=1}^n a_i{\sum_{i=1}^na_i-n\choose n-2}\\ | ||
| + | & =\prod_{i=1}^n a_i\left(\sum_{i=1}^na_i-n\right)^{\underline{n-2}} | ||
| + | \end{split}\end{equation} | ||
| + | $$ | ||
| + | |||
| + | 时间复杂度 $O(n)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int Mod=998244353; | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),s=Mod-n,ans=1; | ||
| + | _for(i,0,n){ | ||
| + | int a=read_int(); | ||
| + | ans=1LL*ans*a%Mod; | ||
| + | s=(s+a)%Mod; | ||
| + | } | ||
| + | _for(i,0,n-2) | ||
| + | ans=1LL*ans*(s+Mod-i)%Mod; | ||
| + | enter(ans); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/contest/arc_106.1613363902.txt.gz · 最后更改: 2021/02/15 12:38 由 jxm2001
