P 教授有编号为 $1 \sim N$ 的 $N$ 件玩具，第 $i$ 玩具经过压缩后变成一维长度为 $C_i$ 为了方便整理，P 教授要求在一个一维容器中的玩具编号是连续的。如果将第 $i$ 件玩具到第 $j$ 个玩具放到一个容器中，那么容器的长度将为 $$x = j - i + \sum\limits_{k = i} ^ j C_k$$。如果容器长度为 $x$。其制作费用为 $(x - L) ^ 2$。其 $L$ 是一个常量。P 教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过 $L$。但他希望费用最小。

矩阵树定理的学习笔记和部分线性代数的知识，记录三道经典题目及变元矩阵树定理。

$h_n = a_1h_{n - 1} + a_2h_{n - 2} + \cdots + a_kh_{n - k}$

求其第 $n$ 项。

给定一个 $N$ 个点 $M$ 条边的有向图。统计无序对 $(X, Y)$ 的个数，其中 $(X, Y)$ 满足存在一条从 $1$ 到 $X$ 的路径，和一条 $1$ 到 $Y$ 的路径，且两路径除 $1$ 外无公共点。

一棵 $n$ 个点，边带权的树，$m$ 次询问，每次给出 $k$ 个关键点，求割掉最小代价的边使 $1$ 号点不能到达任何关键点。

给定一棵有 $n$ 个节点的无根树和 $m$ 个操作，操作有 $2$ 类：

1. 将节点 $a$ 到节点 $b$ 路径上所有点都染成颜色 $c$
2. 询问节点 $a$ 到节点 $b$ 路径上的颜色段数量

游戏中有 $N$ 个剧情点，由 $1$ 到 $N$ 编号，第 $i$ 个剧情点可以经过不同的支线剧情，前往 $K_i$ 种不同的新的剧情点。当然如果为 $0$，则说明 $i$ 号剧情点是游戏的一个结局了。

开始处在 $1$ 号剧情点。任何一个剧情点都是从 $1$ 号剧情点可达的。从任意剧情点出发，都不能再回到这个剧情点。要想回到之前的剧情点，唯一的方法就是开始新的游戏，回到 $1$ 号剧情点。可以在任何时刻退出游戏并重新开始。求花费最少的时间，看完所有不同的支线剧情。

给出一个长度为 $3n$ 的序列，规定连续 $n$ 个数字中不能选择超过 $k$ 个，问最多能取出的数的权值和是多少。

给出一个 $n * n$ 的黑白方阵，问能否通过交换行或交换列使得主对角线均为黑色。

有 $X, Y$ 两类卡牌，分别有 $n_1, n_2$ 张，每张卡牌有三个属性值：$A, B, C$。
两张卡牌能够配对，当且仅当，存在至多一项属性值使得两张卡牌该项属性值互质，且两张卡牌类别不同。
游戏的目的是最大化匹配上的卡牌组数，当然每张卡牌只能用一次。

给出一个 $n$ 个点 $m$ 条边的无向图，每个边有一正一反两个权值；现要从点 $1$ 出发，对每条边经过且仅经过一次；求一种方案使经过的最大权值最小。

给定一个字符串，要求支持两种操作，在当前字符串后加入一个字符串，询问字符串 $s$ 在当前字符串中出现了几次？

后缀自动机的做法相信大家都会，这里记录一下后缀数组做法。

给定一个数 $k$，要求构造一个非负整数序列，使得操作 $k$ 次后，最大数 $\leq n - 1$，每次操作选序列中最大值，将其 $-n$，其余数 $+1$。

给出一个 $1 \sim n$ 的排列，$p_0, p_2, \cdots, p_{n - 1}$，每次从中选相邻两数删去，加入 $q$ 的前面，求最小字典序的 $q$。

维护一棵树，子树修改，询问 $k$ 条链并的权值和。

链接

BZOJ 3589