BZOJ3456 | 有标号无向连通图计数

这玩意可以搞出生成函数然后大力卷积。。直接设 f(n) 为答案,设 g(n)n 个点有标号无向图个数

\text{ans mod 1004535809 }\gets \text{这玩意是个质数, 原根是 3 } \text{ans}=f\left( n \right) g\left( n \right) =2^{\left( \begin{array}{c} n \\ 2 \end{array} \right)} \text{枚举 1 所在的连通块大小} g\left( n \right) =\sum_{i=1}^n{f\left( i \right) \left( \begin{array}{c} n-1 \\ i-1 \end{array} \right) g\left( n-i \right)} 2^{\left( \begin{array}{c} n \\ 2 \end{array} \right)}=\sum_{i=1}^n{\frac{f\left( i \right) 2^{\left( \begin{array}{c} n-i \\ 2 \end{array} \right)}\cdot \left( n-1 \right) !}{\left( n-i \right) !\left( i-1 \right) !}} \frac{2^{\left( \begin{array}{c} n \\ 2 \end{array} \right)}}{\left( n-1 \right) !}=\sum_{i=1}^n{\frac{f\left( i \right)}{\left( i-1 \right) !}\frac{2^{\left( \begin{array}{c} n-i \\ 2 \end{array} \right)}}{\left( n-i \right) !}} \text{生成函数 }F\left( x \right) ,G\left( x \right) ,H\left( x \right) H\left( x \right) =\sum_{i=0}^{\infty}{\frac{2^{\left( \begin{array}{c} i \\ 2 \end{array} \right)}}{\left( i-1 \right) !}x^i} F\left( x \right) =\sum_{i=0}^{\infty}{\frac{f\left( i \right)}{\left( i-1 \right) !}x^i} G\left( x \right) =\sum_{i=0}^{\infty}{\frac{2^{\left( \begin{array}{c} i \\ 2 \end{array} \right)}}{i!}x^i} \therefore H\left( x \right) =F\left( x \right) \ast G\left( x \right) F\left( x \right) =H\left( x \right) G^{-1}\left( x \right) \,\,\left( \text{mod }x^{n+1} \right)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据