传递信息的难点在于每个信息都要是对的，在接受处验证每个信息的正确性，如果信息错误则需要补传送一些信息来告知这个错误位的信息，但是哪一位是错误不可预知。
一种不需要每一位都是对的的信息传递方式是：插值。只要能累计传过去 个正确的点值即可，此事的概率是很大的。
对于任意积性函数 ，和整数 ，这个东西是好求的：
设 表示 ， 为 的最大质因子，那么容斥 的指数，可以得到：
记忆化，并预处理 的 ，并用 筛筛出 的结果。
首先处理的顺序非常确定，从大到小。设 表示剩下 元，需要加多少个硬币；然后就可以 dp 了。
首先 和 只会有一个，否则可以用 和 替代；也不会有两个 ，否则可以换成 和 ；不断更换直到满足上述两个条件为止。
如果没有奇数，那么所有数除以 。
如果有奇数，那么 和 恰好选一个，枚举选哪一个，然后把所有数 后除以二，递归进两种情况去做。总复杂度 。
随便竖着 dp 一下就好了。
的 dp：设 表示前 个数，坐标 ， 是否可达。
优化：考虑一个合法的方案，给它一个随机顺序，那么 最大值的期望只有 。所以直接给所有 idea 随机一个顺序，然后就可以缩小 中 的上限。复杂度 。
提出任意一个生成树，不难发现只要所有点的和是偶数则一定有恰好一组解，否则无解。解的个数其实就是 组。
在圆方树上统计一下就行了。
广义 SAM 随便统计一下就好。当更方便的是树上后缀排序一下也是一样的。
从高位到低位考虑，记下每个数是否顶着上界、是否顶着下界，可以得到 做法。考虑去除无用状态：
既顶着上界又顶着下界：等价于头几位上界下界相同，不需要记下来。
既不顶着上界又不顶着下界：那么剩下的其它位任意，一定存在合法解，可以直接计算答案。
线段树分治维护出每个时刻里和 相连的连通块。需要找到所有这个连通块里还没有被标记过的点。
用一个 treap 状物维护连通块的点集，在 treap 的节点上维护子树内未被标记的结点的个数。
考虑求出不包含的个数。不包含意味着：
然后发现 集合只和它中最大的一个有关， 也只和 中最大的一个有关，那么就简单了，dp 扫过去记下 的最大值、当前在 kmp、SAM 上的结点编号就好。
由于矩阵树定理：一张图的生成树个数，等于其拉普拉斯矩阵的所有非零特征值的乘积除以点数。
完全图的拉普拉斯矩阵的特征多项式为 ，也就带来了 的结论。
设图 的所有特征值为 ， 的所有特征值为 ， 的特征值为 。那么再上生成函数做一下就成了。
拓展：求两张图的笛卡尔积的生成树个数（因为只知道特征多项式而不知道特征值），需要用到结式的知识。
考虑状压最难考虑的是恰好选择了这些位置，而别的自由位不能碰到 有特殊值的地方。考虑容斥掉：
证明考虑乘法分配律。那么现在就不需要恰好了！直接记下可能会在同一列的列集合，就可以 做了。
有另一个做法是：将 视为一个 到 的边，那么就是要选取一个匹配。保留一个生成树，枚举所有非树边的状态，就能做到 ， 为去重后点的个数。两个做法平衡一下得到 做法。
直接维护每条边是轻边还是重边，切换的总次数是 的！考虑换根的过程，只有两根之间的这一条路径上的边以及改变的边的端点相连的一条边会发生改变，原本有 个轻边，后来有 个，总的变化量只有 个。
直接先全改成重边，然后试着找到所有轻边，发现轻边有一个必要条件是 ，这一定会覆盖某一个 。所以维护 ，然后对于所有 ，分别在平衡树上二分找到位置即可。