本文主要是对于一些算法的更为直观或感性的理解，持续更新。
何为容斥？容斥处理集合的交或并。自然，这可以是多个条件的与或或。
Min 和 Max 属于比较严格的限制了（严格到只有一个啊）。那么我们就分解他。
先看看 Min。Min 意味着这个数 $\le$ 所有的数。然而这样限制出来，得到的是所有 $\le$ Min 的数。不过这样形式倒是统一。
那么我们令 $f(x)$ 为 $\le x$ 的数的集合。为了方便，所有数都是正数，这样 $f^{-1}(V)=\left|V\right|$。
那么：
$$
\max(S)=\left|\bigcup_{x\in S} f(x)\right|=\sum_{T\subseteq S}\left((-1)^{\left|T\right|+1}
\left|\bigcap_{x\in T}f(x)\right|\right)=\sum_{T\subseteq S}(-1)^{\left|T\right|+1}\min(T)
$$
Min 同样。
首先，翻面的一定是左边连续一段和右边连续一段。
那么假设我都翻的右面，现在把翻的机会一个个移向左边。提前处理掉一定不会翻的卡牌，可以发现有两个区间：$[\min b_r,a_r]$ 和 $[a_l,\max b_l]$。前者用 ()，后者用 [] 表示，{} 为下一个 []，<> 是上一个。两个区间只会向左移。
答案一定是下述情况：可翻卡牌数饱和；)]}；[({)]}；<([)>]；[()] 的最小值。除最后一种情况都可直接指针扫。而最后一种情况每次事实上是维护一段最值，每次从最前删除，最后加入，可维护一单调队列。
非常笨拙然而是 $O(n)$ 的。
显然有 $n+m-1$ 个自由元，那就设在第一行和第一列。显然每一组自由元的取值唯一对应了一个矩阵。
考虑两个矩阵，他们仅有一个自由元不同。为了保证其它自由元不变，矩阵的变化一定是：在该行或列的元素应依次 $+c,-c,+c,\cdots$。
有一个例外：$a_{1,1}$。如果改变他，则所有的非自由元都会改变。为了统一我们修改第一行和第一列的所有元素。如果再对其他自由元修改使其回复原值，那么所造成的修改就是它应有的修改。
那么钦定这些自由元是 0，求出矩阵原始值。然后进行一些操作：对某一行或某一列（特殊地，第一行和第一列由同一变量控制）进行上述操作。
简意：定义字符串等级为出现在其中至少两次的最高等级的子串的等级 +1，空串等级为 0，求给定字符串的等级。
首先，看到子串的问题，可以想到 SAM。然而任意子串的子串似乎还是不太好表示。在 SAM 上，我们通过边来连接前缀，用 fa 连接后缀。SAM 将子串转化为前缀和后缀。那么类似地，我们对于某一个子串，先继承它前缀的答案，然后用它的后缀，即 Parent Tree 上的祖先来更新。
在进一步的讨论之前，我们先来讨论一个问题：SAM 上一个节点表示了多个串，我们更新答案时肯定等级越大越好，所以我们存一个节点中最长子串的等级。然而这会不会影响“至少出现两次”？最长的子串没有出现两次，有没有可能有更短的子串出现两次？
我们期望它没有影响。现在来尝试证明它：
如果一个短串（非此节点中最长串）在一个串中两次出现，现在将这个短串向前拓展一位 endpos 一定不变，即任何一个位置上拓展都是可行的。那么如果这是长串的末尾，长串也一定可以拓展出去。
那么我们只需维护每一个节点上最长串的等级。
当我们计算一个节点的等级时，它一定不小于其前缀节点答案最大值。而我们再看它至少出现两次的后缀中等级的最大值，最后取最大值即可。
水题，直接单调栈（谐音梗）。
考虑从 $[l,n]$ 转移到 $[l-1,n]$ ，注意到除了 $l$，只有在前一区间中出现在了栈顶，才有可能在新区间中出现在栈顶。维护在区间中所有出现在 $S$ 栈顶的元素，考虑 $l-1$ 对其影响：从前至后弹出不能导致 $l-1$ 弹出的元素，直到一个元素弹出了 $l-1$，此后 $l-1$ 对该区间无影响。
在计算到 $[l,n]$ 时，计算出所有 $[l,r]$，维护的是单调的位置序列，$r$ 对序列没有影响，二分 lowerbound 即可。
$O(n\log n)$
1 |
|
假设我们有一个容器，向其中一个一个加入这些集合。
$n\le 10^5$。
首先，考虑每一个点的贡献：每一个点被选择后，如果不终止，一定随机选择下一个点，计算这之间的期望路径长度（树形 DP）。这样，我们只需计算每个点期望被选择的次数。此时该问题只与节点的值有关。
当已有 $i$ 个点为 $1$ 时，选择值为 $0/1$ 的点的期望次数为：
$$
f_{i,0}=\frac{1}{n}+\frac{f_{i+1,1}}{n}+\frac{i\cdot f_{i-1,0}}{n}+\frac{(n-i-1)f_{i+1,0}}{n}
$$
$$
f_{i,1}=\frac{1}{n}+\frac{f_{i-1,0}}{n}+\frac{(i-1)f_{i-1,1}}{n}+\frac{(n-i)f_{i+1,1}}{n}
$$
整理可得，
$$
(n-i-1)f_{i+1,0}+f_{i+1,1}=n\cdot f_{i,0}-1-i\cdot f_{i-1,0}
$$
$$
f_{i+1,1}=\frac{n\cdot f_{i,1}-1-f_{i-1,0}-(i-1)f_{i-1,1}}{n-i}
$$
我们用 $f_{1,0/1}$ 来表示每一个 $f$，用 $f_{n-1,0/1}$ 的转移列出方程。
如果在一个 $DAG$ 上表示一个字符串的所有子串，朴素的想法是将其所有后缀加入 $Trie$ 中，然而这样节点数是 $O(n^2)$ 的。可以发现，图中节点有很多可以合并之处。
首先是后缀本身。如果先不考虑后缀的公共前缀的存在，那么根本没有必要对每一个后缀都重新存储，可以直接用一条链表示原串，再从根指向各个节点，这样就合并了各后缀，因为只要跳过了开头的一段就可以得到一个后缀。这相当于是 $Trie$ 是菊花图时，把那些后缀拉过来，强行与最长的后缀（即原串）合并，保留那些与根相连的边。图中原串为 abc。
然而后缀可能存在公共的前缀，这使得 Trie 不是菊花图。这样按之前的做法，可能有一个子串出现多次。这不利于解决问题，不是我们想要的。因此 SAM 的一个限定条件是每一个子串都恰好出现一次。
考虑之前做法的本质。由于新加入一个字符 c 时该字符从未出现过，因此增加的子串为所有原有后缀加上 c 和 c 本身，即新的后缀。但如果 c 之前已经出现过，就会出现某些后缀之前出现过，就不能这样加边了。
现在假设我们建好了前 $n$ 个字符的 SAM，现在又加入了一个字符 c。首先一定会与之前的末尾字符连边，这样就有了整个串这个子串。此时新增添的子串一定是原有的能到达的后缀（即，这些后缀是在 SAM 中以到达末尾节点得到的子串，这个后缀除了在后缀的位置上外没有另外出现过）加上了 c，不可能在 SAM 中出现过，否则去掉这个字符一定也出现过。考虑那些之前出现过，但加上 c 后首次出现的后缀。
如果加入之后较大的后缀出现过，较小的后缀就一定也出现过了。因此从大到小考虑这些后缀（此处为原串后缀）。如果某个后缀对应的节点没有 c 的边就连边，否则就停止这一过程。
那么如何考察这些后缀呢？
由于每个子串至多对应一个节点，因此可以在每一个节点存储一个指向上一个子串节点的指针，其指向的节点所表示的子串为与当前节点子串由不同节点表示的后缀中最长的一个，而更短的后缀将递归得到。
$1<n,m\le 10^3,m\le t\le 10^9$
考虑序列的第一位，如果该位确定，那么问题转化为求 $n-1$ 位问题。但这 $n-1$ 位中第一位可能会与整个序列第一位发生合并。我们更希望出现的情况是第一位确定。故设 $p_{i,j}$ 为限制长度为 $i$，首位出现过 $j$ 的概率，即当该序列之前是 $j$ 时发生合并的概率，而在出现了 $j$ 前提下首位保持不变的概率为 $q_{i,j}$。如果第一位保持为 $j$，相当于有后 $i-1$ 位的首位未出现过 $j$，即 $q_{i,j}=1-p_{i-1,j}$。（$j=t$ 时特判，下文不再重复）
当第一位出现了 $j$ 时，可能有两种情况：
在第一位保持为 $j$ 的情况下考虑求解：设以此为前提，期望和为 $g_{i,j}$，则 $ans_i=\sum_{j=1}^{lim}p_{i,j}q_{i,j}g_{i,j}$。设 $f_{i,j}$ 为第一位产生 $j$ 前提下期望和，有：
$$
g_{i,j}=j+\frac{ans_{i-1}-p_{i-1,j}f_{i-1,j}}{q_{i,j}}
$$
考虑求 $f$。讨论 $j$ 是否保持不变，得：
$$
f_{i,j}=q_{i,j}g_{i,j}+(1-q_{i,j})f_{i,j+1}
$$
显然 $lim=\min(n+m-1,t)$，时间复杂度 $O(nm\log(10^9+7))$。但如果不求 $g_{i,j}$，而是求 $q_{i,j}g_{i,j}$，则可以做到 $O(nm)$。
1 |
|
$n\le 3000,m\le 300$
肯定是要算贡献的。
考察一个礼物的贡献，用 $g_{i,j}$ 表示其贡献，即：第 $i$ 种礼物有 $j$ 个，期望被拿走的个数。
考虑从 $g_{i,j}$ 转移到 $g_{i,j+1}$，发现这取决于喜欢这种礼物的人数。考虑有 $k$ 个人喜欢这种礼物的概率，用 $h_{i,j,k}$ 表示前 $j$ 个人中有 $k$ 个人喜欢 $i$ 礼物的概率。此时 $g_{i,j}=\sum_{x=0}^{n}\min (x,j)h_{i,n,x}$，进而 $g_{i,j}-g_{i,j-1}=\sum_{x=j}^nh_{i,n,x}$。
进而买 $j$ 件前 $i$ 种礼物的期望值为：$f_{i,j}=\max(f_{i-1,j-x}+g_{i,x})$。发现 $g$ 的差分不增，故可以转换为贪心，每次寻找 $g$ 增量最大的种类。
此时瓶颈在于求 $h$。
$$
h_{i,j,k}=(1-p)h_{i,j-1,k}+ph_{i,j-1,k-1}
$$
发现我们每次用一个 $\Delta g$ 更新后，只需知道 $\sum_{x=j}^nh_{i,n,x}$，而之前一定已经求过 $\sum_{x=j-1}^nh_{i,n,x}$，故只需求 $h_{i,n,j-1}$，而此前必求过 $h_{i,n,j-2}$，故可以递推，并不需要知道全部 $h$。
复杂度是对的。
可以想到，对于每一个节点，$dp[x]$ 表示其走到终点所需的最少指令数。考虑状态的转移：如果下指令，则 $dp[i]$ 为其出边所通向的点中的最小值加一。若不下指令则取最大值，两种情况取最小值。即，
$$
dp[x]=\min\{\min_{x\to y}\{dp[y]\}+1,\max_{x\to y}\{dp[y]\}\}
$$
你能解决问题的一部分吗？
可以发现下指令的部分类似于一个边权为 $1$ 的最短路，尝试用 $BFS$ 解决。我们先对 $BFS$ 的过程进行一下概括，$BFS$ 时队列中的元素如下：
可以发现，队列中元素（指 $dp$ 值）总是连续的 $n$ 和 $n+1$，且不降。在反图上 $BFS$，每次取队首元素进行更新，从队尾插入。
再考虑不钦定前进方向的情况。（称“第二类”）
枚举 $x$ 的所有出边（在原图上），如果发现指向的点的 $dp$ 值的最大值小于 $dp[x]$，则更新，同时在队首插入 $x$ 以保证单调性在 $x$ 出队时，如果 $x$ 能被第二类更新，显然它应该先被更新再更新别的点，这样不会在非最优值上浪费时间，而此时第二类更新 $x$ 的点一定已经被更新，因此 $x$ 一出队就对其更新，时间复杂度正确，而正确性显然。
