给一个长度为 环染上 种颜色（要求每种都用上），问方案数的最后 位。（）。
由 Burnside 引理再结合上环的个数，再对选的颜色个数进行二项式反演，易得：
欧拉反演一下即可得到：
首先， 的逆元是不存在的，所以我们要通过经典手段——把数表示成 的形式；注意，这里的 还需要压位高精。而 可以用光速幂实现。
用 块 的木板和 块 的木板，问能拼成 的方案有多少种（木板无标号，两块小木板不能相邻）。
容易发现答案是：
写出答案的生成函数：
直接乘进来，可以写成：
于是直接有了其整式递推的形式，矩阵快速幂即可。
更普遍的，若 均微分有限（即可以递推），则 均微分有限。
个排成一列的哨站要进行通信。第 个哨站的频段为 。
每个哨站 需要选择以下二者之一：
- 直接连接到控制中心，代价为 ；
- 连接到前面的某个哨站 ()，代价为 。每个哨站只能被后面的至多一个哨站连接。
请你求出最小可能的代价和。。
批判一下我不是很理想的建图的僵化思维，这里要注意了。
更好的做法：拆点后， 连容量为 的边，然后 连代价为 的边， 连代价为 的边， 连代价为 容量为 的边（思想大概是，分成自己连向中心一个部分，和一个匹配问题两个部分）。
优化建图上，我们发现这是一个二位偏序，所以直接 cdq 分治优化建图就好了。
给定一个长度为 的序列 ，以及 个操作，每个操作将一个 修改为 。第一次修改之前及每次修改之后，都要求你找到一个同样长度为 的单调不降序列 ，使得 最小，并输出最小值。需要注意的是每次操作的影响都是独立的。。
序列上的保序回归问题：
引理：若 ，则 。（调整法易证）。
于是我们可以维护一个单调栈，每次将一些弹栈时都把弹出来的结点合并到一起即可（合并成它们的平均值）。
考虑用可持久化单调栈维护前缀的单调栈和后缀的单调栈，每次查询时就要找到中间哪些节点是要被合并的。
考虑外层先二分一个后缀的前缀，假设这个后缀的前缀都会被合并，先都合并起来，内层再二分前缀的一个最长的能被后缀合并的前缀；再合并起来。判断一下这个新节点能否合并后缀的前缀的后面的第一个点，如果能，；否则，。直接在主席树上二分即可。。
一张无向图，每个点都有一个
0/1权值，每次询问两个点之前是否存在一条回文的路径（不要求简单）。。
首先，我们暴力 dp，设 表示 间存在回文路径，然后枚举 和 之间的所有出边，用类似 bfs 的方式来转移，就能做到 的复杂度。
然后我们惊人地发现，我们可以通过巧妙的方式减少边的数量，减到 级别——先把连接同色的边都拿出来，分成多个连通块，二分图染色一下，二分图子图保留一棵树即可，非二分图就保留一个基环树。连接不同色的边也拿出来进行这个操作，即可。正确定细思显然。
令 表示用 的小木片密铺 的长方形的方案数， 表示密铺 长方形的方案数。求：（ 或 ，）
首先， 是斐波那契数列， 是什么？容易发现 有递推式：
于是我们可以轻松解出其通项公式。然后我们发现 和 的通向公式都可以写作：
统计斐波那契数列的和，常常可以用这个展开式进行优化。组合数没办法直接统计，我们直接写作下降幂的形式：
用第二类斯特林数展开来：
代入通项公式，并二项式定理展开来，移项可得：
直接泰勒公式即可。但是千万要注意，当 时，本公式不成立。
有 个节点，每个节点有两种状态：选中和未选中。
每个选中的点后面都跟着若干个（可能是0个）未选中的点。每个未选中的点都一定跟在某个选中的点后面。
每次操作随机选择两个被选中的点，随机将其中一个变成未选中，且跟在另一个后面，同时将跟在他后面的节点全部改为选中。求这样操作下去，直到最后只剩一个选中的点的期望步数。
这里我们从比较奇怪的角度来解读势能函数法。
一般来说，对于期望问题，我们总是能列出一个方程，形如 ，且 。而怎么解出这个方程就很成问题。
对于特殊的题目，我们可以作一些强烈的假设，然后根据再去验证假设。比如本题中，我们设 。猜想：，其中 为 点的附属点的数量。代入期望方程，得到：
既然是势能函数，我们设 ，再作一次大胆的假设：
解得：。
如果光看这个解释，你可能觉得这个方法简直是无赖！但这背后有着鞅论与停时定理的支持。其成立条件是什么？当然是你的每一步假设都很幸运地成立的时刻。
给出正整数 ，大小为 的整数集 和大小为 的整数集 ，请你求出：（）
我们考虑对于每个形如 的数都统计一下有多少合法。然后我们发现 是循环的，会形成一个大小为 的环；而环的总数当然只有 。对于每个环预处理一下环上前缀和即可。