这里是写题面的 JRY，这一次的题面是不是很资慈呀 ( •̀∀•́ )。

因为之前在造比赛的时候 VFK 点名要让我来写题面，在感觉受宠若惊的同时为了不辜负 boss 的信任，当然要把题面写的生动有趣啦（笑）。

如果大家喜欢的话以后的题面里还是会继续这样写的 (*•̀ㅂ•́)و 。（当然前提是 VFK 还会再让我写题面）

最后插播一个小花絮，其实原来第三题的标题是长这样的：

后来因为它实在是太 ydcydc 了，所以就被无情的改掉啦 (╯°Д°)╯︵ ┻━┻。

公告

我们发现 613，Chloe_fan，xjt 这三位选手的 C 题代码，以及 Chloe_fan，xjt 这两位选手的 A 题代码过于相似，经过管理员之间的讨论，我们决定取消他们这次比赛的参赛成绩。如果这几位选手存在异议，请在评论中提出。

希望各位参赛选手能以此为鉴，掌握开黑的正确姿势（雾），诚信比赛。

实验室外的攻防战

By matthew99

题解By C_SUNSHINE

算法一

我们建立 $n!$ 个点表示所有可能的排列，对于每个点次枚举交换哪两个，就能建出转移边，这样进行bfs就可以了判断 $A$ 状态是否能到达 $B$ 状态了。

这个算法能通过Subtask 1得到 $24$ 分。

不会bfs的戳这里

算法二

我们使用冒泡排序进行模拟，在交换时判断一下，如果经过 $n$ 轮之后仍然不能排成 $B$ 的样子，就输出 "NO"。

这个算法能通过Subtask 1~2得到 $56$ 分。

不会冒泡排序的戳这里

为什么这样是对的呢？因为自信！

算法三

我们可以猜一发结论，假设 $A_{a_i}=i,B_{b_i}=i$，一个显而易见的结论就是如果不存在 $1 \leq i < j \leq n$ 满足 $a_i < a_j且b_i > b_j$，则答案为"YES"，否则为"NO"。 必要性十分显然，假设在 $A$ 中 $i$ 在 $j$ 前，而在 $B$ 中 $j$ 在 $i$ 前，那么一定有一个时刻 $i$ 和 $j$ 相邻且需要进行交换，而 $i < j$，无法交换，所以不可行。 充分性更加显然，考虑冒泡排序的过程，如果存在某一次交换 $i,j$ ($j$紧邻在$i$后面)两个元素时由于 $i < j$ 而无法交换，则一定出现了违反上述必要性的情况，这个命题的逆否命题就是充分性的证明。

那么我们怎么判断是否存在这样的 $i,j$ 呢？

我们按照编号从小到大枚举 $j$，并统计满足 $a_k < a_j$ 的所有 $k$ 中 $b_k$ 最大的值 $b_i$ ，如果$b_i > b_j$ 则说明这种情况出现了。判断完 $j$ 之后，用 $b_j$ 更新位置 $a_j$ ，用树状数组维护前缀和就好。

这个算法能通过全部Subtask得到 $100$ 分。

不会树状数组的戳这里

密码锁

By matthew99

得分情况

一个字形容——惨

49分——SanSiroWaltz 和 BillXu2000

26分——xuhaike

19分——很多人

0分——很多人

算法一

对于subtask1，我们可以枚举每条边的定向，然后暴力求出强连通分量数。

什么你说你不会求强连通分量数？直接floyd跑一遍求传递闭包，把所有的互相能到达的点都缩起来就可以了。当然你也可以BFS。

如果使用$O(n + m)$的求强连通分量的算法，比如tarjan算法，则时间复杂度为$O(2 ^ m (n + m))$，期望得分19分。

算法二

懂逆元的同学都应该知道模意义下统计一个东西的概率，我们可以先统计出强连通分量数的期望，最后乘上$10000 ^ {n(n - 1)}$的数即可。如果不知道逆元可以参考维基百科。可以算出$10000$在模$998244353$下的逆元为$796898467$。

注意到定向后的图是个有向完全图，即竞赛图，竞赛图的强连通分量缩点之后，一定是一个链状的图，满足每个点和后面的点都有连边。

如何统计答案呢，设这张图为$G(V, E)$，注意到答案即为链的长度，链的长度的统计可以转化为链的前缀的数量减一，这条链的前缀显然就是一个点集$S \subset V$，满足所有的$S$与$V - S$之间的连边都是从$S$中的点连出去的，我们定义这样的点集为割集（只是这篇题解中临时引入的定义），那么我们统计割集数量即可。

暴力枚举所有可能的点集$S$，然后直接计算所有$S$与$V - S$之间连边为$S$连出的概率，最后乘起来。

时间复杂度$O(2 ^ nm)$，期望得分42分。

算法三

妈妈我会数学！

对于$m = 0$的情况，大小相同的点集是割集的概率是相同的，对每一种大小的点集很容易计算出该概率以及这种大小的点集的个数，直接统计答案即可。

时间复杂度$O(n)$，期望得分7分，结合前面的算法可以获得49分。

算法四

对于后面的数据，我们发现m比较小，因此最好能想出一个在指数意义上和n无关的算法。

对于一个点集，它是割集的概率无非就是这个点集中的点与点集外的所有点的所有连边都是从这个点集连出去的概率，也就是每条边是连出去的概率乘起来。对于概率非0.5的边我们称其为特殊边，对于大小为$x$的点集，如果其中没有任何特殊边则是割集的概率为$0.5 ^ {x(n - x)}$，如果其中存在一条特殊边，设这条边从$x$连出的概率为$P$，那么这个概率要乘上$2P$，也就是这个特殊边的贡献。我们不妨统计出每个大小的连通块，其中所有特殊边的贡献，最后对每个大小的连通块乘上$0.5 ^ {x(n - x)}$再加起来即可。

一个想法就是枚举有贡献的边的集合，如果一条边有贡献，那么它的两个端点必然有且仅有一个在$S$中，那么我们可以考虑黑白染色，如果染色失败那么一定不存在这种情况，否则我们对于某个连通块，要么黑点在$S$中，要么白点在$S$中，并且每种情况的贡献都容易算出，所以我们通过一个$O(n ^ 2)$的类似背包问题的DP，即可算出每种大小的连通块的贡献总和。

时间复杂度为$O(2 ^ m n ^ 2)$，期望得分73分。

算法五

我们发现之前的复杂度在于背包DP上，对什么进行背包DP呢，对每个连通块进行背包DP，等等你说每个连通块？

一个连通块，如果有$m$条边，那么最多有多少个点，$m + 1$个！我们可以对每个连通块直接枚举哪些点在$S$中，然后计算贡献，最后再来一次类似背包的DP。于是这题就被我们愉快的解决了。代码又短又优美，不比19分的暴力要长。

时间复杂度为$O(2 ^ {m + 1}n + n ^ 2)$，期望得分100分。

a^-1 + b problem

By shanquan2

题解By jiry_2

算法一

直接暴力模拟整个过程，逆元可以通过费马小定理用快速幂求，也可以直接用扩展欧几里得求，这两个方法都是单次 $O(\log n)$的。

时间复杂度 $O(nm \log n)$，期望得分 $10$ 分。

算法二

当没有求逆元操作的时候，我们可以直接更新总和：整体加上 $x_i$ 相当于给总和加上了 $n \times x_i$。直接更新就行了。

时间复杂度 $O(n+m)$，结合算法一期望得分 $20$ 分。

算法三

对于集合中的一个数，我们考虑若干次操作之后它会变成什么。显然每一时刻，都存在常数 $a,b,c,d$，使得原来数列中的每一个数 $A[i]$，它都变成了 $\frac{aA[i]+b}{cA[i]+d}$

于是问题就转化成了，每一次给出一个函数 $f(x)=\frac{ax+b}{cx+d}$，求 $\sum_{i=1}^n f(A_i)$。

当 $c=0$ 的时候，我们可以直接求和，因此接下来假设 $c \neq 0$。

首先，我们可以把 $f(x)$ 给表示成 $f(x)=e+f \times \frac{1}{x+g}$，于是我们只需要考虑求原来的所有数加上某一个数 $k$ 后的倒数和就行了。

因为 $\prod_{i=1}^n (A_i+k)$ 我们可以 $O(n)$ 求出，所以我们可以先给答案乘上这个值，于是我们就只需要求 $\sum_{i=1}^n \prod_{j \neq i}\ (A_j+k)$，不难看出这个也是可以 $O(n)$ 求出来的，这样我们就可以避免掉求逆元的 $O(\log n)$ 啦。

当然，这个做法想要拿到 $50$ 分的话需要加一点常数优化，其中一个方法是：我们可以发现本质不同的询问最多只有 $\frac{m}{2}$ 次，所以可以去掉重复的询问。

时间复杂度 $O(nm)$，期望得分 $30$ 至 $50$ 分。

算法四

考虑优化算法三。考虑算法三中 $O(nm)$ 的部分，第一个地方是求 $\prod_{i=1}^n (A_i+k)$，第二个部分是求 $\sum_{i=1}^n \prod_{j \neq i}\ (A_j+k)$。

先考虑第一个地方，我们构造多项式 $g(x)=\prod_{i=1}^n (A_i+x)$，那么第一部分就相当于给出了若干次询问 $k$，求 $g(k)$ 的值。这是一个经典的多项式多点求值问题，可以用多项式除法解决。至于 $g(x)$ 我们可以通过分治 FFT 得到。

第二个地方的处理方法类似，我们构造多项式 $h(x)=\sum_{i=1}^n \prod_{j \neq i}\ (A_j+x)$，那么也就变成多点求值问题啦。不难发现 $h(x)=g'(x)$，所以在求出 $g(x)$ 之后 $O(n)$ 求一下导就能得到 $h(x)$ 啦。

这样我们就得到了一个 $O((n+m) \log^2 n)$ 的算法，期望得分 $70$ 至 $100$ 分。