Project Euler Problem 918
定义数列 \(\{a_{n}\}\) 满足 \(a_{1} = 1\), 对于 \(n \geqslant 1\) 有:
\[ \begin{aligned} a_{2n} &= 2a_n \\ a_{2n + 1} &= a_n - 3a_{n + 1} \end{aligned} \]定义数列 \(\{a_{n}\}\) 满足 \(a_{1} = 1\), 对于 \(n \geqslant 1\) 有:
\[ \begin{aligned} a_{2n} &= 2a_n \\ a_{2n + 1} &= a_n - 3a_{n + 1} \end{aligned} \]存在初始为空的点集 \(S\), 进行 \(n\) 次操作, 形如:
\(n \leqslant 2 \times 10^{5}, k, u \leqslant 10^{18}\).
这是最普遍的情况, 从树中选取 \(m\) 个结点, 最大化它们的价值之和.
符合直觉地, 设 \(f_{u, i}\) 表示从以 \(u\) 为根的子树中选取了 \(i\) 个结点的最大价值之和. 转移是显然的:
这样转移时间复杂度即为 \(\Theta(nm)\).
有 \(n\) 个物品, 第 \(i\) 个重量为 \(a_{i}\), 求重量不大于 \(c\) 的情况下能够装下的最大重量.
\(n, m = \max\{a_{i}\} \leqslant 2 \times 10^{4}, c \leqslant 10^{9}.\)
给定一颗 \(n\) 个点的树, 求黑白染色的方案数, 使任意一条路径上的黑点数量不超过 \(2\).
\(2 \leqslant n \leqslant 3 \times 10^{5}, \mathrm{mod} = 998244353\).
引理
证明
考虑将重儿子设为链最长的那一个，剖分是简单的，可以做到 \(\Theta(n).\)
这样剖分有一些性质：
由于长链长度之和为 \(n\)，所以我们可以预处理每条链顶端节点的 \(l\) 级祖先，\(l\) 取遍不大于链长的所有整数。并且我们还可以存下每条链的所有节点，挂在链顶。
在一些问题中，我们只关心关键点的信息，同时我们需要维护他们之间的树形结构，于是可以想到将它们和它们之间的 \(\rm LCA\) 拉出来建一颗树，这棵树就被称作虚树。
不难发现这样一定是对的，并且设关键点数量为 \(k\)，则虚树内点数不超过 \(2k\)。
首先建虚树。
若图 \(G\) 中存在一个子图 \(G'\)，\(G'\) 中任意两点均可互相到达，则称 \(G'\) 为 \(G\) 的一个强连通分量。若 \(G'\) 不存在一个严格子图为强连通分量，则 \(G'\) 为 \(G\) 的极大强连通分量。
参考代码：
扫描线模板题，从小到大枚举横线的纵坐标，枚举到矩形下界就给这条边的左右端点构成的区间 \(+1\)，否则 \(-1\)，用线段树维护，当前线段树有值的结点个数就是这个纵坐标的贡献。
当然，本题还需要动态开点，所以需要维护区间内有效点的数量。
考虑用扫描线，维护区间最大值即可。
考虑如何求解以下方程 ：
显然可以转化为 ：
有裴蜀定理 :
对于不定方程 \(ax+by=c\)，其有解当且仅当 \(\gcd(a,b)|c\)。
可以发现上述方程有解当且仅当 \(\gcd(a,b)=1\)，故可以转化为 ：
\(\large\rm Proof:\)
将上式带入下式得 \(:\)
整理得 \(:\)
根据组合恒等式 \(\dbinom{i}{j}\dbinom{j}{k}=\dbinom{i}{k}\dbinom{i-k}{j-k}\) 得 \(:\)
交换枚举顺序得 \(:\)
序列 \(a\) 的普通生成函数 \(\rm(Ordinary\ Generating\ Function,OGF)\) 被定义为形式幂级数 ：
\(a\) 既可以是有穷序列也可以是无穷序列，\(x\) 不具有实际意义，仅作为一个形式上的变量参与运算。
加减不必多说 ：
则有：
由于每一条边都要经过恰好一次，因此对于除了起点和终点之外的任意一个节点，只要进来，一定要出去，故有如下结论：
杜教筛被用来求积性函数的前缀和。
设有积性函数 \(f(x)\)，其前缀和为 \(S(n) = \sum \limits_{i = 1}^{n} f(i)\)。
考虑构造 \(h(x)\) 和 \(g(x)\)，满足 \(h = f \times g\)。
推一下式子 ：
有时候我们需要维护一些具有传递性的关系，如相等，连通等。
初始条件往往是给定几组关系，要把所有的关系求出来。
可以把 Floyd 算法做一些调整：
但是 Dijkstra 算法要求所有边权均非负，于是就有了重赋权的技巧。
接下来证明这样做为什么是对的：
首先有定义 ：
最常用且大部分情况下效率最高的最小生成树算法。
将边按长度从小到大排序，每次贪心选择最短的一条边，若这条边连接的两个点还为连通，则将两个点所在的连通块用这条边连接，连通块用并查集维护。
时间复杂度 \(\Theta(m\log m)\)。
在稠密图上复杂度最优的最小生成树算法。
考虑一些在序列上的区间操作，如区间加和区间求和。
直接暴力做单次操作复杂度是 \(\Theta(n)\)，总时间复杂度 \(\Theta(qn)\).
具体实现如下：
对每个块维护整块加的值，查询的时候加上即可。
时间复杂度 \(\Theta(n\sqrt{n})\)。
差分约束是用来解形如 \(x_{1}-x_{2}\leqslant k\) 的若干个方程的算法。
另外，如果有负环则无解。
时间复杂度 \(\Theta(\rm SPFA)\)。
需要注意的是，最短路求的是以起始点为基准的最大解，而最长路求的是以起始点为基准的最小解。
插值问题形如 ：给定 \(n\) 个点的坐标 \((x, y)\)，要求出一个经过所有点的最低次多项式。
容易构造出 \(f(x)\) 即为下式 ：
正确性显然。
容易证明多项式次数至少为 \(n - 1\) 才可以确保穿过 \(n\) 个点，故最优性得证。
考虑分类讨论 ：
主定理 \(\rm(Master\ Theorem)\) 被用来求解一类递归算法的时间复杂度，假设有递推式形如:
那么根据主定理，有 ：
反悔贪心是对贪心策略的一种优化，有些时候贪心策略是错的，但如果可以撤销之前的操作，那么就会变为正确的。
另外，有一种观点认为反悔贪心的本质是贪心模拟费用流，我认为是有一定道理的，这种观点也有利于解释反悔贪心的正确性。
反悔贪心板子题。
反悔贪心板子题 \(\times 2\)。
称使得 \(a^{t}\equiv 1\pmod p\) 成立的最小正整数 \(t_{min}\) 为 \(a\) 对模数 \(p\) 的阶，记为 \(\delta_{p}(a)\)。
有如下定理 ：\(g_{min}\lt p^{\frac{1}{4}}\)。
小球入盒问题是所有组合问题的基础，它计算的是形如 “\(n\) 个球放进 \(m\) 个盒子的方案数” 的一类问题，在这类问题中一般存在三种限制 ：
理由同上，方案数为 ：
假设有 \(p_{1}\leqslant p_{2}\leqslant p_{3}\leqslant p_{4}.\)
假设一个问题满足四边形不等式，那么它的决策点有单调性。
Proof:
根据最优决策的定义写出这个位置的转移式 :
两不等式相加，得到 :
\(Z\) 算法在国内也被某些人称为 \(\rm ExKMP\)（虽然我不知道它跟 \(\rm KMP\) 算法有什么关系）。
\(Z\) 算法用于求字符串 \(S\) 的 \(Z\) 函数，其定义为 \(z_{i}=\rm LCP(S,S_{i\sim n})\)。
\(\rm Prufer\) 序列可以将一颗结点数为 \(n\) 的有标号无根树用一个长度为 \(n-2\)，值域为 \([1,n]\) 的数列唯一表示，即有标号无根树和 \(\rm Prufer\) 序列呈双射关系。
具体来说，有标号无根树的构建方式如下：
\(\rm Manacher\) 是用于求解一个字符串中所有回文子串的算法。
首先，回文子串的数量级是 \(n^{2}\) 的，所以要考虑如何将所有回文子串快速地表达出来，容易发现如下性质：
考虑枚举右端点 \(R\)，计算对于每个 \(R\) 有多少个左端点 \(L\) 满足条件。
左端点需要满足的条件如下：
转化条件：
时间复杂度 \(\Theta(n)\)。
观察到每个点度数都恰好为 \(2\)，于是连边后构成若干个环。
考虑枚举最大边，分别计算从两个端点出发能走到多少个点。
可以发现并查集能够很好地拟合这个过程，于是将边从小到大加入，每次合并的两个点集即为所求。
时间复杂度 \(\Theta(n \log n)\)。
总时间复杂度 \(\Theta(n^{2})\)。
考虑使用 \(\rm bfs\)。
观察到每一步的代价都是 \(0\) 或 \(1\)，于是建立双端队列。每次迭代取队头，如果走了代价为 \(0\) 的边就将出点加入队首，否则加入队尾。
时间复杂度 \(\Theta(nm)\)。
考虑使用状压 \(\rm DP\)。
考虑记 \(f_{i, u}\) 表示走 \(i\) 步到 \(u\) 的方案数。显然有转移式：
状态数为 \(nk\)，转移的时间复杂度为 \(\Theta(n)\)，于是总时间复杂度为 \(\Theta(n^{2} k).\)
考虑到删除的边数很少，于是将转移方程改写为：
\(2-\rm Sat\) 问题是求解某个 \(\rm bool\) 方程组，方程组中的每个方程被描述为：\(x_{i}\) 为真\(/\)假 或 \(x_{j}\) 为真\(/\)假。
对树上每个点建立一个 \(\rm bool\) 变量，取值为 \(1\) 表示这个点选。
首先可以发现，若不考虑 \(a_{i} \leqslant 10^{6}\) 的限制，那么构造一组合法解是容易的。
同时可以发现，如果对一行或一列进行 \(+1, -1, +1, -1, \cdots \) 操作，那么得到的 \(a_{i}\) 还是合法的。
首先考虑分析 \(f(u, G)\)，可以观察出一些性质 ：
有两个显然的性质 ：
你在一颗树上旅行。
树由 \(n\) 个点，\(n - 1\) 条边构成，每条边的长度 \(w\) 是 \(1\) 或 \(2\)。
给定这棵树和 \(q\) 个询问，每个询问给出 \(u,v,l\)，请求出至少需要多少天。
你是一只僵尸。
你现在和 \(n - 1\) 个僵尸站在一起分配大脑。你的编号是 \(1\)，其他僵尸编号 \(2 \sim n\)。
给定 \(n\)，现在你想活下去，并且获得至少 \(m\) 个大脑，请问至少需要多少大脑才能满足？
首先考虑 \(m = 1\) 的情况。
并查集可以用来维护一类具有传递性的关系，维护形如将 \(x\) 与 \(y\) 所在集合合并和询问 \(x\) 和 \(y\) 是否在同一个集合的操作。
对于普通并查集来说，有路径压缩和按秩合并等优化，路径压缩一般实现如下 ：
按秩合并则取点数小的连向点数大的即可。
顾名思义，字典树就是支持像字典一样加入和查询字符串的树形数据结构，实现如下：
在很多问题中，字符串仅由 \(0\) 和 \(1\) 构成，这些问题存在一定的共性。
考虑如下问题，给一些数，维护它们的异或和，支持插入，删除和全局 \(+1\)。
与线段树合并类似，实现如下：