本来开了某场远古 Div 1，然后学了一堆前置知识至今仍然不会 E。换一场写来得及吗？

A. Channel

模拟，略。

B. Split Sort

Description

给你一个长度为 $n$ 的排列。
每次操作你可以选择一个数 $x$，然后类似于快速排序地把小于 $x$ 和大于等于 $x$ 的分成两个序列，把它们拼在一起。
求最小操作次数使排列有序。

Solution

发现如果 $i$ 在 $i-1$ 前面，只有选择 $i$ 进行操作能改变它们的相对位置。
且操作不会让有序的变无序，那么次数就是 $pos_i>pos_{i-1}$ 的 $i$ 的数量。

C. MEX Repetition

Description

给你一个长度为 $n$ 的序列，保证值域 $[0,n]$ 并且没有重复元素。
一次操作定义为从 $1$ 到 $n$ 对每个 $i$ 用 $\operatorname{MEX}(a_1,a_2,...,a_n)$ 换掉 $a_i$。
求操作 $k$ 次后的序列。$n\le10^5,k\le10^9$ 。

Solution

发现给了 $n$ 个数，值域为 $[0,n]$，那么 $\text{MEX}$ 就是 $[0,n]$ 中唯一没出现那个。
考虑把没出现那个数放在序列最前面，那每次的操作就是交换 $1,2$，交换 $1,3$，直到交换 $1,n+1$。
找找规律可以发现这是个循环移位。
操作 $n+1$ 次一定会回到原状态，因此 $k$ 对 $n+1$ 取模，暴力循环移位即可。

D. Two-Colored Dominoes

Description

给你一个网格，上面放了一堆 $1\times 2$ 的多米诺骨牌。现在要给它们染色，满足：

同一个骨牌的两个格不同色
每行染成黑白的格数相同，列同理
请构造方案。

Solution

发现横着放的骨牌对行没有影响，竖着放的骨牌对列没有影响。
也就是说只要考虑横着放的对列的影响，那么这个可以从左往右一列列贪心，可以证明是对的。

E.Speedrun

Description

你在玩一个游戏，要完成 $n$ 个任务。其中对于每个任务 $i$，它只能在某一天的第 $h_i$ 时刻完成。游戏每天有 $k$ 个小时，分别编号为 $0,1,...k-1$。
给出 $m$ 对任务间的依赖关系，$(a_i,b_i)$ 表示 $a_i$ 必须比 $b_i$ 先完成。保证依赖关系不形成环。
完成任务不需要时间，也就是说可以在同一天的同一时刻先后完成多个任务。

求完成所有任务所需的最短时间。这里的时间定义为：完成最后一个任务的时刻与开始第一个任务的时刻之差。
多组数据，$T\le 10^5$，$\sum n,m\le 2\times 10^5$，$k\le 10^9$。

Solution

假设我们知道每个任务开始做的时间。那么对于边 $(a,b)$，若 $h_a<h_b$，则他们在同一天完成；否则令 $b$ 在第二天的 $h_b$ 时刻完成。使用拓扑排序不难求出最后一个任务被完成的时刻。
同样假设所有没有限制的任务都从同一天开始做，这样并不一定是最优的，比如样例 3 就是反例。也就是说，最优方案是形如把一部分靠前时刻的东西挪到第二天开始做。
而被推迟的任务满足这样几条性质：

每个任务（包括非起点）最多只会推迟一天
被推迟的起点任务是 $h_i$ 的一个前缀

看起来似乎不难理解，所以证明留给读者自行解决。
至此，我们可以先假设它们都在同一天开始，求出答案；再按照 $h_i$ 递增的顺序将起点任务推迟。根据第一条性质，可以记录数组 $flag$ 表示那些点已经被推迟一天；而如果更新过程中遇到已经被推迟过的点，则不必继续更新。

综上，每个点最多只被更新了一次，时间复杂度 $O(n)$。

F. Divide, XOR, and Conquer

为什么不会做呢。/hsh

区间 DP，设 $f_{i,j}$ 表示区间 $[i,j]$ 能否被保留。发现转移是 $O(n)$ 的，总时间复杂度为 $O(n^3)$。

考虑优化转移，先观察异或的性质。设 $s_{l,r}$ 表示区间 $[l,r]$ 的异或和。

考虑区间 $[l,k]$ 什么情况下能从 $[l,r]$ 转移过来 $(k<r)$，那么若 $s_{l,r}$ 的第 $x$ 位为 $0$，不论 $s_{l,k}$ 的这位取几都与另外一半相等。而 $s_{l,r}$ 这位是 $1$ 时，如果这是最高位的 $1$，那 $s_{l,k}$ 这位自然也必须取 $1$；否则因为 $s_{l,k}$ 前面已经比另一半大了，这一位取值无限制。

则 $[l,k]$ 能从 $[l,r]$ 转移过来当且仅当 $s_{l,k}$ 在 $\operatorname{highbit}(s_{l,r})$ 位上是 $1$。

维护 $L_i$ 表示以 $i$ 为左端点，所有能被保留区间出现的 $\operatorname{highbit}$ 值按位或的结果，转移条件为 $s_{i,j}\land L_i \neq 0$。从左侧转移同理，转移复杂度变为 $O(1)$。

G. Swaps

Description

给定长度为 $n$ 的序列 $a$，每次操作可以选定一个 $i$，并 $\operatorname{swap}(a_i,a_{a_i})$。求能通过某种操作顺序得到的不同序列数。

$n\le 10^6$。

Solution

考虑建图。对于每个 $i$，连边 $i \to a_i $。则构造出一个 $n$ 个点 $n$ 条边的图，且每个点有且仅有一条出边。

定义操作 $\operatorname{swap}(a_i,a_{a_i})$ 为“操作点 $i$”。观察对点 $i$ 进行操作后图的变化（不考虑环），发现原图从 $i\to a_i \to a_{a_i}$ 变为 $i\to a_{a_i},a_i\to a_i$。对于交换后不改变序列的情况，形如 $u\to v\to v$，则操作不合法。由于每次操作都对图的结构进行改动不好处理，我们换一种方式，对 $i \to a_i$ 这条边打个标记来表示对 $i$ 进行了一次操作。

假设当前局面的点 $i$，分为两种情况：

点 $i$ 存在一条入边被标记，那实际上的序列里 $i$ 已经是自环了，不能再操作；
点 $i$ 不存在入边被标记，那么我们顺着 $i$ 的出边走，直到找到第一条未被标记的边，把它打上标记。

完成操作后，对于一个给定的标记集合，可以用如下方式构造出实际序列：

若点 $i$ 存在入边被标记，$a_i=i$;
否则，$a_i$ 的实际值为沿着 $i$ 的出边走，第一条未被标记的边指向的点。

对边的标记集合进行计数。设每个点的入度为 $in_i$，且每个点至多有一条入边被标记，则总方案数为 $\prod\limits_{i=1}^n (in_i+1)$。

但不是所有满足这个条件的标记集合都是合法的。考虑图中存在环的情况，并不能构造出一种方案，使这个环的所有边都被标记。因为这个环在只剩一条边未被标记时，实际的序列就已经所有 $a_i=i$ 了。
这同时启发我们发现，对于一个环只有一条边未标记的情况，无论哪条边不被标记，生成的序列都是一样的。那么对于长度为 $k$ 的环 $c_1,c_2,\dots,c_k$，恰有一条边未被标记的方案数有 $\sum\limits_{i=1}^k in_{c_i}$ 种，合法且不重复的方案数为：

\[\prod_{i=1}^k (in_{c_i}+1) -[(\sum_{i=1}^k in_{c_i})-1]-1=\prod_{i=1}^k (in_{c_i}+1) -\sum_{i=1}^k in_{c_i} \]

则总方案数为：

\[\prod_{\operatorname{cycles}}(\prod_{i=1}^k (in_{c_i}+1) -\sum_{i=1}^k in_{c_i})\cdot\prod_{\operatorname{other\ v}}(in_v+1) \]