生成树、Prufer序列的计数问题：0912T1
生成树、Prufer序列的计数问题：0912T1
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132839073
看到生成树计数，很容易想到生成树计数
然后发现每个点有度数限制，我们可以先考虑枚举每个点的度数（也可以是Prufer 序列中的出现次数）
假设出现次数为 ，可以得出其生成树方案为
然后后面是个组合数的形式，然后需要推一堆式子
-
巧拆阶乘换成组合数形式
-
多把无用项移到外面
-
熟练使用范德蒙德卷积
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-11-05
树上贪心+生成树贪心：1104T3
树上贪心+生成树贪心：1104T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134235828 <47.92.197.167:5283/contest/425/problem/3> 根据 nnn 奇偶性可以推断答案 合法解只需要在任何一棵生成树上构造即可 贪心肯定要在最大生成树上 然后从前往后看一条未选的边能不能选即可 123456789101112131415161718192021222324252627282930313233343...
2023-10-19
图论+线性基高斯消元与主元：1019T2 / P4151
图论+线性基高斯消元与主元：1019T2 / P4151 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133932506 http://cplusoj.com/d/senior/p/SS231019B 相当于图上选一条链和一堆环 考虑dfs生成树。 则链是两条从根出发的链 环是每条返祖边组成的环 所以环和链的异或和可以求出来 链的放到线性基里 然后线性基通过高斯消元求主元（贪心思想，主元可以令那一位一定为1。那么就钦定主元为必选，这样一定更优） 高消的...
2023-10-04
组合数与莫队——组合数前缀和
组合数与莫队——组合数前缀和 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133559588 用莫队求组合数是一种常见套路 莫队求 S(n,m)=∑i=0m(ni)S(n,m)=\sum_{i=0}^m\binom n iS(n,m)=∑i=0m(in) S(n,m+1)S(n,m+1)S(n,m+1) 直接做个差，然后就相当于加上 (ni+1)\binom n {i+1}(i+1n) 求 S(n+1,m)S(n+1,m)S(n+1,m) 会麻烦点，...
2023-09-13
根号分治与多项式的巧妙结合：GYM-104386G
根号分治与多项式的巧妙结合：GYM-104386G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132866002 使用范围：序列上对于 每种 数的计数问题 考虑对每种数的出现次数进行根号分治 如果出现次数很少，直接平方暴力即可 如果很大考虑任意 (i,j)(i,j)(i,j) ，我们拆一下，再移一下，然后就变成了卷积形式
2023-09-22
Lucas在与位运算有关的组合数中的应用
Lucas在与位运算有关的组合数中的应用 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133176573 求 (nm) mod 2\binom{n}{m}\bmod 2(mn)mod2 根据 Lucas，有 (n mod 2m mod 2)(n/2m/2)\binom{n\bmod 2}{m\bmod 2}\binom{n/2}{m/2}(mmod2nmod2)(m/2n/2) 也就是 (n&1m&1)(n>>1m>...
2024-01-02
二分图+生成树构造：留下一条边：AT_arc119_d
二分图+生成树构造：留下一条边：AT_arc119_d 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135341327 https://www.luogu.com.cn/problem/AT_arc119_d 首先，我们可以发现，同行和同列的红色格子会相互影响。因此我们可以考虑连边。这里我们容易想到两种连边方式： 红色格子之间连边。 位于 (i,j)(i,j)(i,j) 的红色格子，把第 iii 行和第 jjj 列连边。 考虑第一种连边方式。一...