被虐了.
$sim$
每 $q$ 次操作可以看成一个置换 ,相当于进行了 $\lfloor \frac m q\rfloor$ 次置换和 $m\bmod q$ 次操作.
置换的 $\lfloor \frac m q\rfloor$ 次方可以用快速幂求出,剩下的 $m\bmod q$ 次操作直接模拟就可以了.
$cs$
可以发现一个结论,如果把期望得分分别为 $a,b$ 的两个相邻的裁判 $i,i+1$ 交换,且 $a\le b$ .
那么最终的得分要么不变,要么减少 $1$ .
先考虑它们两人对得分的影响.
- 如果之前他们都投 $1$ ,交换后 $b$ 肯定也会投 $1$ , $a$ 投 $0$ 或 $1$ ,两人总得分不变或减少 $1$ .
- 如果之前 $a$ 投的 $1$ ,而 $b$ 投的 $0$ ,交换之后 $b$ 会投 $1$ ,而 $a$ 会投 $0$ ,两人总得分不变.
- 如果之前 $a$ 投的 $0$ ,而 $b$ 投的 $1$ ,交换之后,要么两者都投 $0$ ,要么 $b$ 投 $1$ , $a$ 投 $0$ ,两人总得分不变或减少 $1$ .
- 如果之前他们都投 $0$ ,交换之后,也都会投 $0$ ,两人总得分不变.
于是得出,交换后两人总得分不变或减少 $1$ .
再考虑交换之后,后面的人总得分变化情况.
- 若 $a,b$ 的总得分不变,后面的人投票情况也不会变,总得分不变.
- 若 $a,b$ 的总得分减少了 $1$ ,后面最多有一个人从 $0$ 变成 $1$ ,而其他人不变,总得分不变或减少 $1$ .
于是得出,交换后全局的总得分不变或减少 $1$ .
把所有裁判按照 $v$ 从小到大排,得分最大,从大到小排,得分最小.
而通过不断交换相邻的两个数,类似冒泡排序的过程,可以让最小值到最大值中每个分数都被取到.
那么当 $p$ 不能取到时,最优的方案就是让得分为最大值或最小值.
当 $p$ 能取到的时,最优的方案就是让得分为 $p$ .
用二分来做不断交换的这个过程.
$count$
考虑每对颜色相同的边 $a\to b,b\to c$ 的贡献,最多会有 $O(n^3)$ 对这样的边.
可以将这两条边删去,加入边 $a\to c$ ,得到了一张新图,贡献即为这张新图的欧拉回路数目.
若新图中, $b$ 的度数为 $0$ ,说明在原图中,任意一条欧拉回路都有 $a\to b,b\to c$ 这部分,贡献就是原图的欧拉回路数目.
否则,得到的新图也是一张弱连通图,可以用 BEST theorem 求解欧拉回路个数.
BEST theorem: 在弱连通图 $G$ 中,若存在欧拉回路,则其数目为
$$
{\rm ec}(G)=t_w(G)\prod_{v\in V} (\deg(v)-1)!
$$
其中 $w$ 是图 $G$ 中任意一个节点,而 $t_w(G)$ 表示在图 $G$ 中,以 $w$ 为根,边由儿子朝向父亲的有向生成树个数.
根据 matrix tree theorem ,这个数目等于图 $G$ 的 Laplacian 矩阵去掉第 $w$ 行第 $w$ 列的余子式.
每次用高斯消元算一遍余子式,时间复杂度 $O(n^6)$ .
考虑怎样由原图的 Laplacian 矩阵得到新图的 Laplacian 矩阵.
可以发现需要将 $(b,a),(c,b)$ 这两个位置 $+1$ ,而将 $(b,b),(c,a)$ 这两个位置 $-1$ .
为了方便,我们选择将第 $b$ 行第 $b$ 列去掉来算余子式,那么对行列式的影响只有 $(c,a)$ 这个位置减少了 $1$ .
考虑矩阵 $A$ 的伴随矩阵 ${\rm adj\ } A$ ,根据定义,它的第 $i$ 行第 $j$ 列是矩阵 $A$ 去掉第 $j$ 行第 $i$ 列的代数余子式.
而当 $A$ 可逆时,有 $A^{-1}=\frac{1}{\det A}{\rm adj\ } A$ ,所以矩阵 $A$ 第 $i$ 行第 $j$ 列的代数余子式就是 $A^{-1}_{j,i}\cdot \det A$ .
那么把 $(c,a)$ 这个位置减掉 $1$ ,对行列式的影响就是减掉 $A^{-1}_{a,c}$ 乘上原来的行列式.
对于每个 $b$ 都要求一次去掉第 $b$ 行第 $b$ 列后的逆矩阵,时间复杂度 $O(n^4)$ .
上面那个做法瓶颈在求 $n$ 次逆矩阵,尝试进一步优化.
考虑用高斯消元求逆矩阵的过程,如果消掉了除了 $x$ 之外的元,那么提取出逆矩阵,将它去掉第 $x$ 行第 $x$ 列也是对的.
于是可以分治消元,定义函数 $solve(l,r)$ 表示当前 $[l,r]$ 内的元还没有消.
当 $l=r$ 时,表示其它元都消过了,于是就得到了原矩阵去掉第 $x$ 行第 $x$ 列后的逆矩阵.
否则,将 $[l,mid]$ 内的元消掉,调用 $solve(mid+1,r)$ ,将 $[mid+1,r]$ 内的元消掉,调用 $solve(l,mid)$ .
时间复杂度 $O(n^3\log n)$ .