被虐了.
A 清扫银河
先做一个生成森林,然后本质的环就只有非树边对应的至多 $m - n + 1$ 个,其他环都可以由异或线性组合出来.
现在只考虑操作 $1$ ,一个图能被若干个环异或得到,当且仅当所有节点度数是偶数.
而这若干个环都可以在那 $m - n + 1$ 个环形成的基底下被分解.
所以只要状态为 $1$ 的边形成的子图中,每个点度数为偶,就可以在至多 $m - n + 1$ 次 $1$ 操作内将所有边都变成 $0$ .
考虑恰当安排 $2$ 操作达到这个条件.
$2$ 操作的贡献可以摊到每个点上,可以看做选出一个点集 $S$ ,若某个点被选了,就把它所连的边颜色全部翻转.
转化后可以看出,多次 $2$ 操作可以合并成一次,所以总操作不会超过 $m-n+2\le m +1$ 次.
做一个 01 高斯消元,第 $i$ 个变量表示 $i$ 有没有被选,第 $i$ 个方程是点 $i$ 的度数在异或意义下为 $0$ .
用 bitset 优化,时间复杂度 $O(T\cdot \frac{n^3}{w})$ .
B 通用测评号
可以把猎人杀的思路借用过来.
由于每个位置没有差别,可以算出所有位置达到 $b$ 时,第一个位置达到 $a$ 的概率,乘上 $n$ 就是答案.
考虑容斥,枚举集合 $S$ 在第一个位置到达 $a$ 的时候还没有到达 $b$ ,由于所有位置相同,所以只需要枚举 $i=|S|$.
再枚举一个 $j$ ,表示第一个位置到达 $a$ 时,那 $i$ 个位置上的总和为 $j$ .
每次选位置时像猎人杀那样,若选到了已经 $=a$ 的位置就重新选,直到选到可以放的.
那么我们只会关心这 $j$ 次操作和第一个位置的前 $a-1$ 的操作的相对顺序,它的第 $a$ 次操作相对顺序一定在最后.
$$
ans=n\cdot (1-\sum_{i=0}^{n-1} (-1)^i \binom{n-1}{i}\sum_{j=0}^{(b-1)\cdot i}\binom{a-1+j}{a-1}\cdot \frac{f(i,j)}{(i+1)^{a+j}})
$$
其中 $f(i,j)$ 表示有 $i$ 个位置和 $j$ 次操作,要求每个位置被操作次数 $<b$ 的方案数.
由于每次操作是有区别的,所以方案数就等于 $(\frac{x^0}{0!}+\frac{x^1}{1!}+\dots+\frac{x^{b-1}}{(b-1)!})^i$ 这个多项式第 $j$ 项的次数乘上 $j!$.
用 NTT 实现多项式乘法,时间复杂度 $O(n^3\log n)$ .
常数优化: 多项式 $(\frac{x^0}{0!}+\frac{x^1}{1!}+\dots+\frac{x^{b-1}}{(b-1)!})$ 可以只进行一次 DFT, 保存点值即可.
C 前进四
将所有修改和询问分别按照下标 $x$ 从大到小排序,从大到小枚举下标.
对于每个时间 $t$ ,维护当前后缀 $x$ 的最小值,以及这个数随着 $x$ 的减小被修改的次数,后者就是需要查询的答案.
考虑将 $x$ 相同的修改操作按照时间从前往后排序,相邻两个修改操作会影响一段时间区间内的后缀 $x$ 最小值.
那么这段区间维护的最小值需要对修改的值取 $\min$ ,并且需要维护变小的次数,以及支持单点查询.
用一个 Segment tree beats 维护以上操作.
时间复杂度 $O(n\log n)$ .
常数卡不过去了.