一半看到这种代价为 \(k\) 次方的形式，且需要转移复杂度的题，都是用第二类斯特林数解决的
第二类斯特林数我们记作 \(\begin{Bmatrix} n \\\\ m \end{Bmatrix}\) 表示将 \(n\) 个相互作区分的元素放入 \(m\) 个不做区分的集合里，每个集合元素非空的方案数，我们很容易就能有多项式得到一个恒等式
我们不妨计 \(\begin{Bmatrix} n \\\\ m
\end{Bmatrix}\times m!\) 的 egf 为 \(f\)，即集合做区分的母函数，考虑另一个
egf 为 \(g_n\) 满足
\[ g_n=\sum_{i}i^n\frac{x^i}{i!} \]
这道题做法很常规，考场上rush失败了QwQ
我们设 \(d_{n,k}=\sum[d|n^k]\) 那么显然对于 \(n\) 唯一分解后，\(d_{n,k}=\prod_{i=1}^n(kc_i+1)\)，\(c_i\) 质因数的质数
简单无向图的可视化，根据 Erdős–Gallai 定理将度数序列
\(d\) 排序可得，若满足
\[ \forall k\in[1,n],\sum_{i=1}^kd_k\le k\times(k-1)+\sum_{i=k+1}^n\min(k,d_i) \]
这道题考完之后一直也没题解，蒟蒻就自己找了些资料，一知半解地写了这道题，主要参考 NERC2019 C.Cactus Revenge 和 Cactus graph realization of degree sequence，接下来的事情也主要复读这两个资料的
我们在之后的讨论中设度数序列为 \(d\)，图的点集大小为 \(n\)，边集大小为 \(m\)，首先有个很明显的性质即
树的直径具有许多优美的性质，我们将在以下几题探讨
树上一个点与其对应最长简单路径的另一端点一定是直径的端点，即直径的最长性，除此之外，直径上会存在中点，具有很好的对称性
考试时多项式推错惨遭爆零
首先，这道题很明显式子是一个二项卷积，考虑 EGF
不妨设
\[ f=\sum_np^n\lfloor\frac{n}{k}\rfloor\frac{x^n}{n!} \]
时隔 \(9\)
个月，终于肝出这题了
设恰好有 \(i\) 条边不重复的方案数为 \(f_i\)
\[ f_i = \sum_{|E|=i}\sum_{E'\subseteq E}(-1)^{i-|E'|}n^{|E'|-1}\prod_{S=C(E')}s \]
给定程序，求程序地期望运行结果
考虑一个长度为 \(n\) 地排列，其逆序对数地期望为 \(\frac{\binom{n}{2}}{2}\)，由此，不妨设 \(f_n\) 为长度为 \(n\) 的排列期望运行结果，则有
\[ f_n\ =\ \frac{n(n-1)}{4}+\frac{1}{2^n}\sum_{i=0}^n\binom{n}{i}f_i \]
给定一个数字三角形，最底下一层的值为一个长度为 \(2n-1\) 排列，其余方格中填写的整数是方格正下方,左下方和右下方方格中所写整数的中位数，给定 \(n\) 和 \(x\) 求最终构造出三角形顶端为 \(x\) 的方案
一开始想的是每一层的值比下一层的值少了下一层的最大值和最小值以及满足比周围 \(4\) 个方格的树都小或都大的数，所以我们需要要计算好中位数偏移量，将左侧每 \(3\) 个数将需要删除的数移进去即可，得到的结论是 \(|n-x|\le\lfloor\frac{n}{3}\rfloor\) 时 \(x\) 可以构造出来，这个构造意外的骗了很多分
给定 \(n\) 张值为 \(i\) 的卡牌，每次随机选择一个整数 \(m\)，将每 \(m\) 张合成 \(1\) 张卡牌值加 \(1\)，剩下的卡牌丢掉，直到最后只剩下一张牌，求值的期望
题意有些不清楚，首先 \(m\) 张牌合并的意思是将 \(n\) 张牌依次排列，依次把相邻的 \(m\) 张牌只合并 \(1\) 次，新的牌的值就是原来 \(m\) 张牌的值的任意一张加 \(1\) 剩下的丢掉，注意可以自己和自己合并
明确了意思就不难做出来了，显然任何局面下的每张牌面的牌面都一样，所以设 \(E(n)\) 为有 \(n\) 张牌时，每张牌值得期望，则有
\[ E(n)\ =\ \frac{\sum_{i=1}^n[E(\lfloor\frac{n}{i}\rfloor)+1]}{n} \]