Solutions

嗯首先我们先思考如何通过模和乘法凑出任意一个数。 我们很容易想到我们可以用两步操作，我们指定一个大质模数（比如 1e9+7），然后我们找 $\cfrac{b}{a} (\mod 10^9+7)$ 作为乘法即可。 然后我们想到把操作的一个点用来做乘和模，然后剩下一个放到最后一个点。 然后我们就可以在 $2n-2$ 次操作内把前 $n-1$ 个都归到任意我们想要的值。 然后我们想把最后一个也归位，但显然只有一个数不行的，我们想想两个数。不妨考虑 $n=2$ 的情况。 我们首先想到，我们如果目的是给一个数乘上一个数且后面一定要取模的话，那实际上我们可以把这个数调得很大（因为你后面肯定要取模，可以加后面那个模数的整数倍）然后这样对另一个数就没有影响了。 然后显然取模你是没有什么办法能避免的。 然后我们还发现最后一次一定会把某个位置的值乘上某个数，这提示我们不妨倒序考虑。 我们相当于说找 $a$ 的一个因子 $x$，使得其 $> b$，然后可以使 $a$ 除以 $x$，$b$ 加上 $x$ 的任意倍。 然后懒了，开始打表。 结果打出来一坨几百个边的图，在 graph editor 里抽搐。 只能推结论了。

牛牛题。 首先你把答案 reverse 一下，就是指定一个根，然后每次扩展一个相邻于当前连通块的点。 先考虑如何 check。 首先一个 native 的想法是考虑两种方向相反的 DFS 序。 然后你发现一个菊花图就把你 hack 了。 然后另一个 native 的想法是用两个根这样做。 但实际上你通过跑一下你发现还是会出问题，然后你看一下相同的两棵树，你发现他们一般动一两条边，然后他们分别连的都是同一连通块。 这启示我们从一个点连到哪个点进行考虑。 我们注意到我们根据一个拓扑序来构造一棵树的话，本质上你是把每个点选择一个前面的点挂上去。其实跟整个树的结构无关。你只关心每一步了连到了哪个点。 然后我们就想，如果对于两个拓扑序来讲一个点都能挂到前面的两个点上，那是不是就不唯一了呢？这个感觉是非常对的。 形式化的来讲，你对每个 $i$ 都找出 $i$ 在每个拓扑序中的位置，然后把前面的所有数的集合交起来。如果存在一个 $i$ 使得该集合大小超过 $1$ 则不合法。 然后你趁洗澡的时候对拍，然后回来发现拍了四万多组了都没出问题，就把他当对的了。 然后接下来的思路，你灵光一现，想到我们其实不怎么关心是怎么遍历的，我们关心的是从哪个点开始遍历的。 然后我们就想一条边他是怎么被经过的。然后你发现除了连接叶子的边其他边都要被正反经过一遍。 我们把叶子剥了，把每个里叶子都作为起点扫一遍就能做到。（这个显然是下界） 然后我们发现这个图的性质很优雅。我们发现这样一并把原来的性质满足了。 但我们还要考虑叶子怎么放置。我们发现我们直接紧贴着放在里叶子的后面即可。因为你发现这样一定不会重。 然后就做完了。 啊？ 等等，然后怎么做答案呢。 直接做即可。 我好厉害。 你发现你输出解会有点问题。 但不慌，你扰动一下，你每次把 $G$ 翻转一下。 然后就过了！！！

首先“三元环”触发关键词。 在竞赛图中若有环则一定有三元环。 然后我们再套路地把竞赛图进行 SCC 缩点是一条链。 很容易知道如果一个 SCC 不是链的最后一个他只能是一个点，因为若不是，则有三元环，而他们都指向后面，因此不合法。 显然我们要重点考虑最后一个 SCC。 然后呢就不会了，看一眼题解。 我们现在考虑找 SCC 中的一个点 $u$，并把他的前驱后继分开来。 显然前驱必须是一条链。 后继呢可以手玩。假设不是一条链，则一定有一个三元环，如果这个三元环都指向了一个点，那不合法，如果没有的话，则一定指到了 $u$ 的前驱，然后我们拿 $u$，那个前驱，指向前驱的点作为三元环，如果满足一定条件他们一定都指向三元环下一个点。反正啰里啰唆的，分讨即可。懒得写。于是后继也必须是一条链。 然后怎么做呢？ 然后我们通过手玩发现其实这个条件是充要的。具体来讲你反证法然后一定能推出一个矛盾。 然后他就像一个厚厚的甜甜圈一样，基于一个环。 主要是怎么 DP 的问题。 这个不愧是2000pts的题目完全做不出来。 严肃研读题解。 大哥我错了，这个题怎么这么难。 你主要是你对这个甜甜圈计数，

有趣题。 首先答案相当于要求三个矩阵里枚举三个点，然后求 AB 的路径数乘上 BC 之间的路径数加起来。 然后这个东西呢，我们先考虑假如 A 和 B 都固定的情况，我们发现是一个矩形。 然后我们根据一个叫曲棍球棒恒等式的东西我们很容易写出其为： $$ f(x_r + 1, y_r + 1) + f(x_l, y_l) - f(x_r + 1, y_l) - f(x_l, y_r + 1); $$ 然后我们就有平方做法了。 然后我们怎么继续优化？ 我们首先发现这个式子是可以拆的，拆成十六个问题，每个问题相当于给起点和终点要求午饭点。 然后我们还是想着差分对吧，然后我们就把他差分成：午饭区域是一个以起点为左下角的长方形。 然后我们惊奇的发现我们可以枚举我们从哪个边界出这个矩形的，因为我们知道了这个之后我们可以方便算出有多少种方案，更重要的是——在经过固定边界的一条路径上的午饭点的数量是相同的，我们直接乘起来就可以了。 然后就大概是超大常数 $O(n)$。

简单题。 首先看到这个题目第一眼就要想到结论：$n$ 个在 $[0,1]$ 间均匀随机的数的第 $k$ 小期望是 $\cfrac{k}{n + 1}$。 这个范围相当宽裕，我们只要给出一个 $O(\text{poly } n)$ 的即可 然后我们考虑枚举答案所在区间，我们现在枚举到了 $[t - 1, t]$。 然后我们想知道有多少个随机数落在这个区间里，多少个落在区间左，多少个落在区间右。我们如果知道这些我们可以直接通过那个结论算出对应的期望。 然后我们就是想要知道在钦定了左中右的数量后有多大概率。 我们可以使用二维背包，直接做即可。时间复杂度四次方。

简单题，但脑抽了。 这个题目本质上就是让我们算这个每个位置的系数。（因为他可以通过类似哈希来检验你的系数，就算你有不算出系数的方法，那通过他的不同数据一定能唯一确定系数） 好的我们很容易得到一个 $O(n^3)$ 的做法，设 $f_{i,j}$ 为第 $i$ 轮第 $j$ 个数的系数，然后枚举你当前选择哪一个。然后便是 $O(n^2)$ 的。你发现对每个 $f_{i,j}$ 他只从 $f_{i-1,j}$ 和 $f_{i-1,j-1}$ 转移过来。然后就方了。 如何继续优化？显然你可以把每轮的除以 $i-1$ 和除以 $2$ 拎出来。然后你对着剩下的表进行干瞪。你通过瞎试发现他一定是 $\binom{i-1}{j-1}$ 的倍数。然后你对他除完之后的进行因式分解。然后发现除完之后是两个双阶乘的积。然后你就糊里糊涂地做完了，但并不知道这个组合意义。这不乏为一种方法但多少有点唐了。 然后说正解，实际上你发现我糖丸了。你还可以继续拎。具体思想就还是考虑不变量以及图论建模。我们把他变成在自动机上走，然后你发现你每增加 $j$ 就会乘上固定贡献，每增加 $i-j$ 也会乘上固定贡献。于是我们发现这两个贡献与你走的路径无关，乘上的东西都是一定的。然后贡献就是两个双阶乘，而你的路径数就是 $\binom{i-1}{j-1}$。

这是一个“分步”进行构造的过程，每一步关联不大。所以我们先研究每一步有什么性质。 假设你现在有长度为 $n$ 的序列，你需要在第 $i$ 个元素之后插入一个 $x$，字典序变大当且仅当？ 你考查你插入后的序列，找到那个你插入的元素。其后面第一个第一个与前一个数字不同的数字比他前面的数字大，或者其后面的所有数字相等。 好吧我错了。 考虑加元素是困难的，考虑删元素。 然后你发现对于一个连续段来讲你删任意一个都是等价的，所以我们钦定每次删最右边那个。 这相当于每次删 $a_i > a_{i+1}$ 的地方。这看起来容易多了。 我错了，我好菜。 我们设 $f_{i,j}$ 为考虑长度为 $i$，值域为 $k$ 的。 我一直在试图一个一个加，结果发现还是做不了。 主要是你发现这个东西你还是要知道全局信息。 题解说：我们分治！ 然后你直接枚举 $1$ 的出现位置和出现时间，然后分成前后两半。 做完了。 为什么我这么蠢啊。

首先把如果 $b > r$ 那肯定选蓝，一定不劣。 然后我们就再把 $r-=b$ 然后就变成了你选一个子序列使得 $\sum r - 逆序对数$ 最大。 然后我们显然 DP 记录前面用了多少个 $0$。 $f_{i,j}$ 表示当前考虑了 $[1,i]$ 的下标，前面用了 $j$ 个 $1$。 然后转移显然好转移，考虑优化。

首先我们发现其实这个东西是可以分类讨论的。 对于 $(2i-1,2i)$ 这样的二元组讨论。 若两者都不是 $-1$ 则直接跳过。（甚至可以直接离散化掉） 若两者都是 $-1$ 则可以放在一起算。具体来讲，我们可以数一共有多少个这样的二元组，然后我们只要算全是 $-1$ 的答案，然后再乘上把这些二元组去掉之后的答案即可。（因为对于其他的二元组确定的情况下，实际上的方案数总是相同的） 比如有 $k$ 个二元组，然后你考虑钦定哪些数作为二元组中的更小值，然后再排列一下。钦定的方案数为 $Catalan(k)$。因为注意到你本质上要求对于任意前缀，选的作为最小值的个数 $\ge$ 作为最大值的个数。然后排列即为 $k!$，即答案为 $Catalan(k)k!$。 现在我们只要专心考虑恰好有一个 $-1$ 的即可。 我们先考虑简单的情况，假设整个排列都是一个 $-1$ 和一个非 $-1$。 然后这个时候开始 DP。 我们发现这个顺序根本不重要，我们只要给他们染色然后配对即可。最终再乘上阶乘。 我们如法炮制，还是按值域排在一起，发现我们可以从大到小做。 我们称已经被填入的为白点，我们要填的是黑点。 设 $f_{i,j,k}$ 为当前处理了值域在 $[i,n]$ 内的东西，其中钦定 $j$ 个 $[1,i)$ 中的黑点，$k$ 个 $[i,n]$ 内的黑点已经被预留了。 然后直接转移即可。 调半天过不了样例。 问题在于，实际上你不能在 dp 的时候简单地只看你留了几个来考虑这个 $(-1,-1)$ 二元组，你要把他放进去算，因为实际上这个预留与实际上还是有一些区别的，因为你可能可以填上这个东西。

我意识到了我做 DP 的严重问题。我非常习惯于说去推结论和性质，结果迟迟没有开始试图设计状态。对 DP 理解的非常的不深刻。在推性质的时候应该主动像 DP 上靠。而不是先推再说。要主动地设计状态，尝试几种经典的状态设计。然后试图找出关系。或者是先找出子结构之间的联系。 DP 的本质就是子结构。要主动洞察这个题目有哪些子结构，以及他们之间的良好性质，而不是仅靠“发现”。 我觉得我设计暴力 DP 这件事比 DP 优化更困难。因为我并没有养成这种良好的思维习惯。 开始正题。 这个题目首先就是我们 feel 一下这个题目。 一个 native 的想法是考虑从小到大以 popcnt 为层推进。然后呢你其实可以把他看成一个金字塔。然后你想一下，比如说你当前先把单个元素染个色。然后对于横跨的，怎么办？实际上对于这些横跨的不能随便染色，反例：RBBR 13 24 R 14 23 B 然后就炸了。 然后呢我就摆了，也许是畏惧吧。 你其实可以推进一步，你思考为什么会炸。 因为 R 和 B 的并都是 S。 然后显然 R 和 B 的并不能都不是 S。 然后如果 S 是 R 那一定是 R 的并是 S。反过来同理。 实际上现在你可以直接开始试图设计状态了。 比如你很经典地你设 $f_{S,0/1}$ 为 $S$ 内染色，然后颜色为 $0/1$。然后这个时候你想怎么转移。 你发现你好转移啊，你找这个并不是当前颜色的并。然后你发现其实这个并一定得是对应的 $f$ 然后你直接转移即可。 优化用脚优化。你直接一个一个加即可，套路。