谢罪环节

组题的zhouyuyang本来是想拿这场给UR的难度退退烧，特意给三道题都放了较多的部分分。

结果C出题人matthew99和验题人zhouyuyang一直不知道这道题曾经在清华集训2012中出过类似的题，同时也将部分分放得过于宽松，造成了巨大的放送事故。

因此带来的问题zhouyuyang代表本场的管理员向大家谢罪。

本场难度比以往的UR简单许多，大家可以把这场UR当成UER来做。

清扫银河

from hdmmblz，数据 by peehs_moorhsum，标程、题解 by zhouyuyang。

一血是 Iittle_waxberry。

算法1

我会暴力!

枚举所有可行的操作大力出奇迹。

时间复杂度$O(??)$

期望得分:$0 \sim 40$。

算法2

我会优化暴力!

找出原图的生成森林。则对于每条非树边均形成了一个环。

不难证明所有的简单环均可以通过若干次非树边形成的环进行异或得到。

同时对于操作2我们可以拆成若干次单点操作，如果一条边的两个端点均被操作或均为操作则颜色不变，否则颜色改变。

因此有用的操作种数至多为$m+1$，直接跑一次高斯消元解异或方程组，判断是否有解即可。

时间复杂度$O(\frac{Tm^3}{w})$。

期望得分:$70$。

算法3

我会找性质！

性质:我们称所有颜色为1的边形成的子图为目标子图，对于一张图，若目标子图种所有节点度数均为偶数，则总可以通过$m-n+1$次操作得到一组解。

证明:设所有简单环通过异或操作得到的线性空间为环空间。考虑所有$m-n+1$条边代表的简单环。显然这些简单环为环空间的一组基。因此环空间的维数为$m-n+1$。

同时，所有节点度数为偶数的图均在环空间内，因此总可以通过不超过$m-n+1$次操作将所有边变为白色。

因此我们可以将异或方程组的方程个数和未知量个数减少至$n$。异或方程组的限制是关于节点度数的限制。

由于多次操作2总可以合并至一次进行，因此至多进行一次操作2，总操作次数为$m-n+2 \le m+1$。

时间复杂度$O(\frac{Tn^3}{w})$。

期望得分:$100$。

通用测评号

from ridiculos，数据、标程、题解 by zhouyuyang。

一血是 supy。

算法1

我会暴力！

将每种数字出现的次数压入状态。

不难发现状态个数至多为$\binom{2n}{n}$。

时间复杂度$O(\binom{2n}{n}n)$。

期望得分$20$。

算法2

首先注意到答案和操作次数没有关系所以可以认为每次随机选择一个框子放球，而忽略掉只选择没放满的框子的限制。

枚举满了的框子数量 $d(1 \leq d \leq n - 1)$, 我们只需要计算搞到 $d$ 个满框的概率。

令 $S(z)$ 为 $\sum \limits_{i=0}^{z}{\frac{x^{i}}{i!}}$.

我们把每次放球的框子的编号写成一个序列，并写出合法序列方案数的生成函数。

我们强制一个框子为最后一个变成半满的，再强制确定所有的满框子。设最终共有$d$个满的框子，则关于序列长度的生成函数可以表达为:

$$[e^{x} - S(a - 1)]^{d} \times [S(a - 1) - S(b - 1)]^{n-d-1} \times \frac{x^{b-1}}{(b-1)!}$$

将$[e^{x} - S(a - 1)]^{d}$部分二项式展开，得到:

$$(\sum \limits_{i=0}^{d} \binom{i}{d} \times e^{ix} \times [-S(a - 1)]^{d-i}) \times [S(a - 1) - S(b - 1)]^{n-d-1} \times \frac{x^{b-1}}{(b-1)!}$$

$[S(a - 1) - S(b - 1)]^{n-d-1}$ 和 $[S(a - 1)]^{d}$ 可以通过NTT来快速计算。

现在问题转化为若干个$a_{i} \times x^{i} \times e^{jx}$的求和问题,其贡献为:

$\begin{align} & x^{i} \times e^{jx} \\=&\sum \limits_{k=0}{\frac{(k+i)! \times j^{k}}{k! \times n^{k+i+1}}} \\=&\frac{i! \times n^{-i} \times (\frac{n}{n-j})^{i}}{n - j} \\=&\frac{i!}{(n-j)^{i+1}} \end{align}$

这里出现$n^{k+i+1}$的原因是:因为我们计算的是方案数关于长度的生成函数，因此要将概率删去，而计算时没有统计的最后一个元素也要计入。

对于每个 $d$ 别忘了乘上 $\binom{d}{n} \times (n - d) \times d$，这代表着钦定最后一个半满框子和所有满框子位置的方案数。

总复杂度$O(n^{3} \times k \times log(nk))$. 除去NTT部分之外常数很小。

期望得分:$50$。

算法3

from matthew99。

在验题时matthew99给出了一个比上面优秀的算法。

考虑每个框子在全部半满之前被填满的概率，方便起见这里我们计算的是$1$号框满的概率，最终只需要将答案乘以$n$即可。

考虑枚举在$1$号框满的时候没有半满的集合$S$。

显然在确定半满集合时我们只关心$S$和$1$中球排列的相对顺序。因此可以进行简单的DP。

设$f_{i,j}$表示前$i$个元素，总共填了$j$个球的合法操作序列数，可以进行简单转移。

则可计算出$|S|=i$时在所有框之前填满的概率$=\sum \frac{f_{i,j}}{(i+1)^{j+1}}$。

最后进行一次简单的容斥问题即可。

若使用$FFT$优化复杂度可优化至$O(n^3 \log n)$

期望得分:$70 \sim 100$。

Bonus:本题存在$O(n^3)$做法，选手可以自己思考一下。

前进四

from matthew99，数据、标程、题解 by zhouyuyang。

算法1

我会暴力！

直接模拟题目大意。

时间复杂度$O(n^2)$。

期望得分:$10 \sim 25$。

算法2

我会分块！

将数组分为$\frac{n}{S}$块，每块大小为$S$。

维护每个块内的所有不同的后缀最小值。

询问时由于最终被选中的后缀最小值显然为当前块后缀最小值的某一个前缀，因此可以通过二分快速计数。

时间复杂度$O(n \sqrt{n \log n})$。

期望得分:$50 \sim 70$。

算法3

我会线段树！

采用线段树维护一段区间内的所有不同的后缀最小值。

在两段区间合并时后缀最小值序列可以看成是左儿子序列的前缀和右儿子序列拼接起来的结果。

这提示我们可以采用可持久化的数据结构来维护后缀最小值序列。

由于需要支持可持久化的分裂和合并操作，因此可以使用fhq_treap或者可持久化线段树维护。

时间复杂度$O(n\log^2n)$。

期望得分:$50 \sim 70$

算法4

算法三的序列维护部分占用的大量空间。

实际上算法三并不需要维护这个序列。

我们可以在合并过程中通过后缀min来更新每个节点是否可能作为后缀min节点。

因此只需要支持线段树区间加，区间询问最小值个数即可。

空间复杂度可优化至$O(n)$。

期望得分:$70 \sim 85$

算法5

考虑按照数组下标扫描线，维护关于时间的后缀min的线段树。

需要维护以下两种操作：

• 区间求min。
• 单点询问这个值被取min了多少次。

采用Segment tree beats维护即可。

因为没有区间加操作因此使用Segment tree beats的时间复杂度为严格$O(n \log n)$。

期望得分:$85 \sim 100$。

seg beats入门

下面简单介绍下 segment tree beats。

如果我们只需要求出一个节点的min，只需要线段树维护区间min即可。

但是如果我们需要求一个节点被取min了多少次，这个问题变得很难维护。

我们对于每个节点维护区间最大值和最小值，修改时一直在线段树上递归到权值最小值比取min的值要大的节点。这样子就可以支持取min次统计了。

很可惜的时，这样子复杂度仍然是$O(nq)$的。

但是我们考虑一下一种特殊情况，如果一个区间内除了最大值，其余所有值均比取min的值要小的情况下，类似的我们可以维护一个最大值被取min了多少次的标记。

当在线段树上递归到如是节点时，只修改最大值和最大值的标记即可。

乍一看复杂度非常不正确，但是可以证明复杂度是$O(n\log n)$的。

这是因为考虑所有权值大于$min$的点。每出现了一次次大值超过min的情况，就会导致权值连续段个数减少$1$。同时一次操作至多增加两个断点。势能分析一波即可。

如果对此有兴趣的同学可以参阅WC2016中吉如一和罗哲正的营员交流，那里有更加详细的描述。