定义
如果我们知道\(\{ f_n \}, \{ g_n \}\)有这种情况时：
\[ f_n = \sum_{i = 0}^n a_{ni} g_i \]
那么我们就可以用已知的\(f_0, f_1, \dots, f_n\)的值来求出\(g_n\)：
\[ g_n = \sum_{i = 0}^n b_{ni} f_i \]
上面这种求值方式叫做反演。
泰勒展开
定义
对于一个函数\(f(x)\)，如果该函数在其定义域上处处可导，则可以写成一个多项式函数（也就是这个函数的泰勒展开）。一般的，我们有：
\[ f(x) = \sum_{n = 0}^{\infty} \frac{f^{(n)}(x_0)}{n!}(x – x_0)^n \]
当\(x_0 = 0\)时，这个式子亦成为麦克劳林级数。
P3317:「SDOI2014」重建题解
矩阵树定理的运用
正常来讲，在矩阵树中，我们其实要算的东西就是这个：
\[ \sum_T \prod_{e \in T} p_e, \forall p_e = 1 \]
我们算的其实就是概率都为\(0/1\)的情况。现在我们要算：
\[ \sum_T \prod_{e \in T} p_e \prod_{e \notin T} (1-p_e) \]
我们可以考虑写成和式内仅与矩阵有关的式子：
\[ \sum_T \prod_{e \in T} p_e \frac{ \prod_e (1 – p_e) }{\prod_{e \in T} (1-p_e) } \]
合并积和式：
\[ \prod_e p_e \sum_T \prod_{e \in T} \frac{p_e}{1 – p_e} \]
然后我们把矩阵的内容改成\( \frac{p_e}{1 – p_e} \)就行了。
P3345:「ZJOI2015」幻想乡战略游戏题解
主要解法
动态点分治真不友好。
我们先来考虑\(O(nq)\)的静态做法。我们可以随便定一个根，\(O(n)\)处理两个数组来记录子树的权值和与子树之外的权值和，然后再来一次\(O(n)\)判定答案是否最小。
其实从这个地方，我们可以发现一些关系：如果一个点的子节点比父节点更优，会有这样的关系：
\[ dist(fa[u], u) * (sum[fa[u]] – sum[u]) < dist(fa[u], u) * (sum[u]) \]
其中\(sum\)数组是子树的权值和。总结一下就是：
\[ 2 * sum[u] > sum[fa[u]] \]
「Fortuna OJ」Jul 11th – Group B 解题报告
A – 照片
这道题是一道很考察思维的题目，我在这里介绍 DP 的做法。
我们考虑 DP。大概的方程可以写成：
\[ dp[i] = max\{ dp[j], j \in S_i \} + 1 \]
其中，\(dp[i]\)代表\([1, i]\)之间最多的斑点奶牛数量，然后\(S_i\)就是我们可以转移来的区间。我们可以提前处理好每一个点对应的\(lft_{S_i}, rig_{S_i}\)，也就是每一个点集合的左右端点。这个区间满足一个根本的条件：这个区间是点\(i\)左边最近的、不包含\(i\)的集合。我们肯定可以从这一段区间搞出最大的答案。预处理的时候先默认\(rgt[i] = i – 1\)，最后做个小 DP 更新数据即可。
BZOJ 3456:城市规划题解
题面
注意：这道题在 BZOJ 上是权限题，我是在 JZOJ 上做的。
刚刚解决完电力网络的问题，阿狸又被领导的任务给难住了。
刚才说过, 阿狸的国家有\(n\)个城市，现在国家需要在某些城市对之间建立一些贸易路线, 使得整个国家的任意两个城市都直接或间接的连通。
为了省钱，每两个城市之间最多只能有一条直接的贸易路径。对于两个建立路线的方案, 如果存在一个城市对，在两个方案中是否建立路线不一样，那么这两个方案就是不同的，否则就是相同的。现在你需要求出一共有多少不同的方案。
好了，这就是困扰阿狸的问题。换句话说，你需要求出\(n\)个点的简单（无重边无自环）无向连通图数目。
由于这个数字可能非常大，你只需要输出方案数 mod 1004535809(479 * 2 ^21 + 1) 即可。