本文用以记录曾经做过的组合数学和生成函数
神秘小结论
范德蒙德卷积：
类似公式：
思考方向就是先插入一个断点，然后确认断点后，再一一对应，本质上就是 n + m + 1 个中选出 k + 1 个。
还有另一种形式，
一般用于组合数的化简，或者利用 \begin{pmatrix} x \\ n \end{pmatrix} 是一个 n 次多项式的性质反演优化计算（类似上升 / 下降幂）
令 g(k) 表示分为允许为空、两两不同的 k 个集合， f(k) 表示不允许为空、两两不同的 k 个集合。那么有，
二项式反演，我们可以得到
然后考虑两两相同，直接除以 k! 消序即可。
就可以得出，
记 F_n(x) = \sum \begin{Bmatrix} n \\ k \end{Bmatrix} x ^ k ，考虑其递推式，
此时构造出 G_n(x) = e ^ x F_{n - 1}(x) ，对其求导数并代入，
由于 F_0(x) = 1 ，则 G_0(x) = e ^ x ，考虑直接展开代入，
可以得出，
令 F_n(x) = \sum \begin{bmatrix} n \\ k \end{bmatrix} x ^ k
由于 F_0(x) = 1 ，则 F_n(x) = x ^ {\overline{n}} 。
然后二项式定理计算点值平移，倍增 O(n\log n) 计算，提取系数即可。
一个数列 \{a_n\} 的指数生成函数
然后可以发现如果两个指数生成函数相乘可以使得其变为：
这是指数生成函数最直接的应用，但是一般来讲可能都被理解为了 \{\dfrac {a_n} {n !} \} 的普通生成函数。
对于错排来讲， D_n = (n - 1)(D_{n - 1} + D_{n - 2}) 。
然后稍加推导有 \dfrac {D_n} {n !} = (-1) ^ n + \dfrac {D_{n - 1}} {(n - 1) !} 。
这说明其指数生成函数 \hat{F}(x) = x\hat{F}(x) + e ^ {-x} ，可以推出 \hat{F}(x) = \dfrac {e ^ {-x}} {1 - x} 。
朴素的分治乘可以做到 O(n \log ^ 2 n) ，此处记录用二项式定理优化的解法：
这个东西就只需要反转多项式然后乘就好了。
以上升幂为例：
x ^ {\overline{2n}} = x ^ {\overline{n}} (x + n) ^ {\overline{n}} 。
这个就是直接倍增求可以做到 O(n \log n) 。
然后考虑边界条件 F(a, 0) = \begin{pmatrix} n \\ a \end{pmatrix}, F(0, b) = \sum_{i = 0} ^ b \begin{pmatrix} b \\ i \end{pmatrix} = 2 ^ b
大力 O(m ^ 2) 递推即可。
我们现在考虑 k 个颜色的答案是什么，然后可以列出一个式子：
稍加计算，
但是我们发现，这样是会算重的，主要是在于剩下 (m - k) 个可能也会恰好出现 s 次，于是我们思考怎么去掉重复贡献。
假设我们记 f(k) 表示上面的式子的答案， g(k) 表示我们要求的答案，就会惊奇的发现，
直接二项式反演，
可以看见这是一个减乘卷积，按照套路反向生成函数：
然后 G(x) = F(x)e^{-x} ，直接卷积就行了，复杂度 O(m \log m) 。
这道题可以用到上面的神秘技巧，通过二项式定理化简规避上升 / 下降幂的复杂计算。
令 f(x) = \sum_{k = 0} ^ m \begin{pmatrix} x \\ k \end{pmatrix} g(k) ，上面说明了这样做的可行性。
那么二项式反演 + NTT 就可以 O(m \log m) 得到 g(k) 。
然后将 f(x) 用 g(k) 换掉，
直接 O(m \log m) 计算即可。
首先，注意到这是一个错排问题，那么就可以考虑 n 个全错排数为 f(n) 。
那么答案就是 \begin{pmatrix} n \\ k \end{pmatrix} ^ 2 2 ^ k k! f(n - k) 。
接下来只用考虑 f(n) 如何计算。
可以同一般错排一样思考，假设加入第 n 个座位，那么要求一定不是情侣，一共有 2n(2n - 2) 种选法。
分类讨论，如果被占用的情侣与当前没有坐在一起，那么就是 (n - 1) 个的全错排，贡献为 g(n - 1) ；
如果坐在了一起，考虑同一排位置与在哪一排，剩下 (n - 2) 个全错排，贡献为 2(n - 1)g(n - 2) 。
于是可以得到递推式 g(n) = 2n(2n - 2)(g(n - 1) + 2(n - 1)g(n - 2)) 。
大力递推，查表得答案即可。
因为无根树非常棘手，我们先考虑有根树。
记 f_{i, j} 表示大小为 i 的树，以 j 颜色为根的答案。
为了方便计算，我们记 g_{i, j} 表示大小为 i 的树有 j 个任意子树的答案， h_{i, j} 是子树不能是黄色为根的答案。
那么显然，红色 f_{i, 0} = g_{i, 0} + g_{i, 1} + g_{i, 2} + g_{i, 3} ，蓝色 f_{i, 1} = g_{i, 0} + g_{i, 1} + g_{i, 2} ， 黄色 f_{i, 2} = h_{i, 0} + h_{i, 1} + h_{i, 2} ，因为考虑到还有向父亲的连边。
接着考虑 g 与 h 的转移，这是一个类似背包的转移：
组合数是因为可以选择重复的形态的子树。
考虑完有根数，开始思考无根树的内容，我们发现 重心 可以充当无根树的根。
那么对于重心的子树大小不超过 \lfloor \dfrac n2 \rfloor ，所以遍历有根树的大小只到 \lfloor \dfrac n2 \rfloor ，然后答案理论上就是 2g_{n, 0} + 2g_{n, 1} + 2g_{n, 2} + 2g_{n, 3} + g_{n, 4} + h_{n, 0} + h_{n, 1} + h_{n, 2} + h_{n, 3} 。
但是，考虑到 n 为偶数时，重心有两个，这说明是会算重的，所以考虑去除这一部分。
考虑两个重心的连边，分成 \dfrac n2 的两棵子树，当且仅当其不同时需要去重，这一部分是 \dfrac{(f_{\frac n2, 0} + f_{\frac n2, 1})(f_{\frac n2, 0} + f_{\frac n2, 1} - 1)}{2} + f_{\frac n2, 2}(f_{\frac n2, 0} + f_{\frac n2, 1}) 。
然后枚举有根树大小，暴力贡献 g, h ，可以做到 O(n ^ 2) 。
注意到这是一棵树，那么考虑到一个子树 u ，其左右子树为 l, r ，s_u 表示子树的大小。
考虑 DP ，因为最小值是要当根的所以是剩下 (s_u - 1) 个数中选出 s_l 个，故有转移方程：
暴力转移即可，时间复杂度 O(n \log _m n) ，可能会用到 Lucas 定理。
首先，我们直接对原串做括号匹配，如果说没有匹配， ( 匹配至 n + 1 ， ) 匹配至 0 。
接下来思考 K 级偏值的含义，其实就是 K 重的子串嵌套。
对于原串的一个左括号 i 考虑，其匹配的右括号为 j ，那么要想有贡献，第一重嵌套一定不能包含 j 且要包含 i ，而其他的并无要求。
因此，我们可以知道 K 重嵌套的左端点的贡献就是 \begin{pmatrix} K + i - 1 \\ K \end{pmatrix} ；右端点考虑容斥，即全部可能减去包含 j 的，也就是 \begin{pmatrix} K + n - i \\ K \end{pmatrix} - \begin{pmatrix} K + n - j \\ K \end{pmatrix} 。
右端点同理可得其贡献为 \begin{pmatrix} K + n - i \\ K \end{pmatrix} \Bigg(\begin{pmatrix} K + i - 1 \\ K \end{pmatrix} - \begin{pmatrix} K + j - 1 \\ K \end{pmatrix} \Bigg) 。
时间复杂度 O(N) 。
首先，很显然的，想要成环的话，剩下来的只能是若干条链，或者一整个环。
因此，对于 m > n ，显然无解； m = n 的答案等价于 n 的全圆排列，但是翻转认为是同构，所以是 \dfrac {(n - 1) !} 2 ； m = 0 ，显然只有 1 。
观察到链的翻转很有说法，而孤立点不可翻转，所以考虑枚举孤立点个数 d 。
剩下的链可以看成序列的分割，即一个长度为 n 的序列分成 (n - m - d) 部分，记第 i 段为 [p_{i - 1} + 1, p_i] 。
然后，我们可以认为 p_{i - 1} + 1 < p_i 且 1 < p_1, p_{n - m - d - 1} < n - d - 2 。
这个形式不好看，根据套路 p_i'= p_i' - i ，变为 p_{i - 1} < p_i 且 1\leq p_1, p_{n - m - d - 1} \leq m - 1 ，那么插板可知方案数是 \begin{pmatrix} m - 1 \\ n - m - d - 1 \end{pmatrix} 。
那么考虑除去分割点外有 (n - d) ! 的排列总数，但是考虑到链的交换与翻转，所以需要除以 (n - m - d)! 2 ^ {n - m - d} 。
那么孤立点数目是范围的 [\max\{0, n - 2m\}, n - m) 。
答案就是
可以 O(\sum n) 计算。
考虑一个朴素的做法，枚举 |S| ，大力 DP ，可以做到 O(n ^ 3) 。
观察到模数是非常奇怪的 U ^ V ，部分分中有一个 U | a_i ，而 U, V 都很小，似乎引导着我们向令 |S| = Ux + y 思考。
然后只要在做乘法的时候选择 Ux 项的次数大于等于 V ，那么这一块都是 0 。
同时， |S| 的枚举范围可以因此减小至 U ，然后将 DP 状态再加一维选择 Ux 的次数，仍然是树上背包大力合并。
时间复杂度可以做到 O(U V ^ 2 n ^ 2) ，稍微有点卡常。
首先 cnt_i ^ 2 是一个经典 trick ，转化为选出两条长度为 l 的同色链的方案数。
然后大力 DP 是这样的 f_{u, v, x, y} 表示两条链分别走到 u, v ，链长分别为 x, y 的方案数，这个是 O(n ^ 3 l ^ 2) 的。
然后考虑到染色统计答案的需要，这么 DP 确实不太方便，于是考虑令 f_{u, x, y, c} 表示两条链上一次重合在 u ，链长分别为 x, y ，且重合恰好 c 次。
显然可以发现恰好 c 次不好维护，考虑二项式反演，改为至少 c 次，记作 g_{u, x, y, c} 。
然后我们可以 O(n ^ 3 l) 预处理出 h_{u, v, x} ， u \to v 恰好走 x 步的方案数。
然后转移就是 g_{u, x, y, c}h_{u, v, i}h_{u, v, j} \to g_{v, x + i, y + j, c + 1} ，这个东西分开卷积是 O(n ^ 2 l ^ 4) 的。
那么如何优化呢？观察式子。
假设 p_i 是至少 i 次， q_i 是恰好 i 次。
答案的式子就是：
发现 i 的枚举是没必要的，只需要乘系数 (k - 1) 即可。
时间复杂度 O(n ^ 3 l + n ^ 2 l ^ 3) 。
考场上一点没看，觉得是输出方案数就输出了 1 ，喜提 4pts ，查分的时候都蒙了。
首先思考 k = 1 ，每个点的度数是 d_i ，答案就是 \prod_{i = 1} ^ n (d_i - 1) ! 。
然后考虑 k > 1 ，那么直接容斥，只需要思考对于一棵生成树怎样才能使得能从多起点出发得到。
我们发现，显然只有当所有起始边在原树的一条链上时才会算重。
因为如果在 u 为根的树内存在 3 个直接相连的子树有钦定边，那么把 u 与这些子树相连的那几条边拎出来，这几条边在生成树上是在一条链上的，而要钦定边作为起始边，一定位于链头或者链尾，那么也就是最多只有 2 个子树内的边能当起始边，这也就说明了其在原树上在一条链上。
然后对于链上的点由于方向定了，起始结束的边都必须确定，所以只会有 (d_i - 2)! 的可能，其实就是带有了 \dfrac 1{d_i - 1} 的点权，由于在链上所以不用考虑 d_i = 1 的情况。
那么就是考虑计算对于一个有点权边权链的计数问题。
考虑枚举子树根 u ，对于其某个儿子 v ，分类讨论求 x \to u 且 x 在子树内的系数和 f_u ：
如果 (u, v) 是一个起始边，我可以选或不选（这两种容斥系数相加为 0 ），相比不选的情况，多了一种只选 (u, v) ，所以贡献是 -1 ；
否则，我只能不选，贡献是 (d_u - 1)f_y 。
接着由于是链，那么一定又两条子树内的链拼接而成，假设分别是来自 x, y 两棵子树，那么我们会发现，还是同上如果 (x, u) 是一个起始边，那么是 -1 ，否则是 f_x ， y 亦同理，答案就是两两系数相乘。此时，我们只要前缀和一下系数再乘一个 d_u - 1 ，求和即是答案。
我们只要处理出统计答案的系数即可，其实不太需要求出 f_u ，时间复杂度是 O(N) 的。
首先根据常识， Fibonacci 序列的生成函数是 \dfrac x{1 - x - x ^ 2} 。
然后题目要求的是 \dfrac 1{1 - \dfrac x {1 - x - x ^ 2}} ，化简一下就是 1 + \dfrac x {1 - 2x - x ^ 2} 。
然后 1 + 后面的式子，可以变为一个高中课内的二阶线性递推：
获得特征方程 x ^ 2 = 2x + 1 ，解得特征根 x = 1 \pm \sqrt 2 。
然后代入 a_1, a_2 解得系数为 \pm \dfrac 1 {2 \sqrt 2} ，可以得到 a_n = \dfrac 1 {2 \sqrt 2} \Big((1 + \sqrt 2) ^ n - (1 - \sqrt 2) ^ n \Big) 。
考虑生成函数， f(x) = \prod_{k = 1} ^ n \Big(\dfrac {1} {1 - x ^ k} \Big)^ {a_k} ，已知 f(x) 求 a_k 。
按照套路同取 \ln ， - \ln f(x) = \sum_{k = 1} ^ n a_k \ln (1 - x ^ k) 。
对右侧式子 \ln (1 - x ^ k) 求导再 Taylor 展开再积分：
代回原式，
接着按照套路 T = ik ，
然后提出系数 T[x ^ T] \ln f(x) = \sum_{d | T} d a_d ，然后直接套一个莫反， Dirichlet 卷积即可。
时间复杂度为 O(n \log n) ，但是要写任意模数 NTT ，会非常难受，反正我被卡精度折磨疯了，直接套了别人的板子。
