【习题选讲】一些「有趣」的计数题
都是 2019 暑期训练题～
燕归巢(swalllow)
枚举不同形态的树显然不可能，所以我们可以考虑一条边的贡献（这在之后的计数题是很常用的技巧，可以说是套路了，一定要掌握！
先将结点分为左右两个集合，枚举左边集合点数 i，那么右边集合点数则为 n - i；
选择左边点集共有 C(n - 1, i - 1) 种方法（注意要减一！因为连接两个集合的边，也就是被考虑贡献的边，它的一端是不被计入的）；
左边形成的树有 i ^ {i - 2} 种形态，右边形成的树有 (n - i) ^ {n - i - 2} 种形态；
选择连接左集合和右集合的边 共有 i(n - i) 种方法；
选择包含这条边的路径 共有 i(n - i) 种方法。
所以就是:
$\sum\limits_{i = 1}^nC(n - 1, i - 1) i^{i - 2} (n - i)^{n - i - 2} i (n - i) i (n - i)$
头皮屑(Venus)
（有趣的标题
实质是数论题。考试时找到了性质：
- 至少一个是质数且至少一个数 > n / 2，无边相连，为 0
- gcd > 1，有直接边，为 1
- 互质，最小质因数之和 <= n，为 2
- 互质，两个数都 <= n / 2，为 3
我们在讨论中忽略数字 1。
4）直接用总边数减去 0）1）2）就好了。
建议看 CF 原题解：传送门
坐等memset0(memset)
非常妙的 CF 题！
我们发现，f(l, r) = l ~ r 的点数 - l ~ r 的边数。
那么我们可以拆开 sigma，计算每一个点的贡献和每一条边的贡献，就可以 AC。