CF1236

$Div.2$

贪心地拿,先拿 $b,c$ 组合的,不能拿时再拿 $a,b$ 组合.

显然答案为 $(2^m-1)^n$ .

进行 $n$ 轮填数,第 $i$ 轮将 $(i-1)\cdot n+1\sim i\cdot n$ 这 $n$ 个数分配给 $n$ 组.

每轮中,若给某组填入该轮的第 $x$ 个数,则该组的 $sum$ 加上 $x$ .

每轮填数前将所有组按照 $sum$ 从大到小排序,依次从小到大填入 $n$ 个数.

模拟走的过程,只有撞上障碍点或者边界时才拐弯.

用 $set$ 将所有障碍点和边界存下来,每次根据当前方向,二分出下个拐弯的位置,走的时候记录访问过的格子数目.

若某个时刻,走过的格子数目达到了 $n\cdot m-k$ ,就说明找到了一组合法解.

可以发现,以某个确定的起点出发,可能的终点一定是一段连续的区间.

只需要找出这段区间的左,右端点.

若能向左走,就走,否则留在原地,可以找出左端点,同理可找出右端点,但这样暴力找是 $O(n^2)$ 的.

考虑遍历数组 $a$ ,当前的第一个元素只会对某个位置的起点有影响,将它们全部移开.

若当前在找左端点,就移到右边,否则移到左边,用并查集实现.

需要特判 $n=1$ 以及 $a_i=1$ 或 $a_i=n$ 的情况.

对于一棵仙人掌,每个点最多在一个环上,删掉某些点后,每个点仍然在最多一个环上.

记点数为 $a$ ,边数为 $b$ ,环的数目为 $c$ ,于是连通块数目 $X=a-b+c$ .

方差可以看做 $E(X^2)-E(X)^2$ ,而 $X^2$ 可以拆成 $a^2+b^2+c^2-2ab-2bc+2ac$ .

根据期望的线性性,答案为
$$
E(a^2)+E(b^2)+E(c^2)-E(2ab)-E(2bc)+2E(ac)-(E(a)+E(b)-E(c))^2
$$
把这 $9$ 种情况的贡献都统计进去,需要计算逆元,时间复杂度 $O(n\log P)$ .