prime

数论

题意：分别求 1*n、2*n、3*n、... n*n 关于模 p 的逆元。p 是质数，n < p。

初步解法：暴力枚举。因为 a 关于模 p 的逆元 b 满足 ab mod p = 1，而 b < p，所以可以枚举 b。但是由于没有用 long long 导致爆零。

（下文用 ie(x) 表示 x 关于题目中 p 的逆元，且下文中的运算均在 mod p 的前提下）

正解：由于 ie(a) = a^p-2，所以我们可以先用快速幂求出 n! 的逆元。由于 ie 是积性函数（见注释），所以 ie(n!)=ie((n-1)!)*ie(n)，即 ie((n-1)!)=ie(n!)*n，所以就能用线性时间求出 2~n-1 的阶乘的逆元。同样由上个式子可以推出，ie(n)=ie(n!)*(n-1)!，所以又可以用线性时间求出 2~n 的逆元。（1 的逆元始终是 1）最后再用线性时间求出 ie(a*n)=ie(a)*ie(n)。

注释：ie 是积性函数，（不严谨的）证明如下：

设 x 是 a 关于 p 的逆元，y 是 b 关于 p 的逆元，即 xa mod p = yb mod p = 1，则

xayb mod p = 1

?(ab)*(xy) mod p = 1

即 xy 是 ab 关于模 p 的逆元，即 ie(ab) = xy = ie(a)*ie(b)。

??

color

线段树

题意：在线段上进行涂色，每次对一个区间涂色都会影响到区间的两个端点，在询问时，相邻两个点之间的开区间的颜色也计入总颜色中。如，假设 [1, 2] 先被涂成颜色1，然后端点1被涂成颜色2，端点2被涂成颜色3，则询问区间 [1, 2] 时总的颜色种数为 3。颜色总数少于 60 种。

初步解法：直接普通的点线段树，写了三个多小时还是爆零。

正解：最棘手的问题就是两个相邻点之间的开区间的颜色如何保存。其实也很简单：将每个区间的左右端点扩大到原来的两倍，则区间的中点就可以用来表示中间这段开区间。所以正解不过就是把区间端点扩大两倍然后进行普通的点线段树操作即可。

关于颜色数的统计：无法直接从左右子树的颜色数得到总区间的颜色数，因为左右子树中的颜色可能有重复。而由于颜色种数不多，可以考虑用一个 64 位整数表示某个区间上有哪些颜色，那么对左右子节点的颜色值进行按位或操作即可得到总区间的颜色值。然后统计颜色值中有多少个1即可。

??

threefour

树形动规

题意：假设在一棵有根树上存在五个互不相同的节点，分别记为 a，b，c，d，z，若这 5 个点同时满足以下要求：a，b，c，d，lca（a，b），lca（c，d），lca（lca（a，b），lca（c，d））这 7个节点互不相同，并且 z 是 lca（lca（a，b），lca（c，d））的祖先；那么五元组（a，b，c，d，z）表示了一棵合法的"不三不四树"。同时，交换a，b，c，d，z的顺序只算作一种。现在给定一棵以 1 号节点为根的树，求满足上述要求的"不三不四树"的总数。输出答案mod 1234567891后的结果。

初步解法：考场上写完第二题已经只有 15 分钟了，直接写了个 rand() 骗分然后打扫雷去了。

正解：其实是比较明显的树形 DP 题。

「不三不四树」的最终形态是这样的：

（两节点不一定相邻，中间可以隔几个点）

用 f(x, 0) 表示在以 x 为根的子树中（包括 x）任选一个，一共有多少种方案；用 f(x, 1) 表示在以 x 为根的子树中（包括 x）任选三个，一共有多少种方案；用 f(x, 2) 表示在 x 的左右子树中各选三个，一共有多少种方案（x 的左右子树各选 3 个对应了「不三不四树」的底下两层，x 作为「不三不四树」的第二层）。

很明显，f(x, 0) 即以 x 为根的整棵子树的节点数。

f(x, 1) = sum{ f(i, 0)*f(j, 0) } + sum{ (k, 1) } i, j, k 是 x 的子节点

解释一下：f(x, 1) 表示在整棵子树中任选三个构成一棵满二叉树的方案数，那么有两种情况：构成的树的根节点是 x 或不是 x。如果构造出的树的根节点是 x，那么再在不同的两棵子树中各选 1 个即可，由乘法原理，可得上式的第一部分；如果根节点不是 x，那么根节点必然在子树中，所以加上子结点的 f(x, 1) 即可。

f(x, 2) = sum{ f(i, 1)*f(j, 1) }

由于 f(x, 2) 表示构造出的树以 x 为根，所以不用加上子树的 f(x, 2)，用类似于上面那个递推式的第一部分的方法计算。

则最终答案为 ans = sum{ f(x, 2)*depth(x) }，depth 从 0 开始计算。（depth(x) 就代表了 x 有多少个祖先结点，x 的任意一个祖先结点都可以作为整棵「不三不四树」的根）