2018 Multi-University, HDU Day 2

Problem A

Upsolved by ultmaster.

题意：有一堆随机变量 $x_1,\ldots,x_n$，其中 $x_i \sim U(l_i,r_i)$。求 $|x_1+\cdots+x_n|$ 的期望。

题解：官方题解给的解法一，尝试实现，两个小时后放弃。而解法二，说实话，写得太过意识流了。

其实两个解法都把题意转化成了这样一个问题：一开始给一个函数 $f(x)=|x|$，然后对 $i$ 从 $1$ 到 $n$，每次令 $f(x) = \frac{1}{r_i - l_i} \int_{x+l_i}^{x+r_i} f(x) \text{ dx}$（也就是说前 $i$ 个的和，加上某个未知数 $x$ 的期望，这个未知数加上去是为了下一步方便转移。）

然后解法一就暴力地求分段解析式。为了让复杂度对，似乎还要用维护两端的滑动窗口。打扰了。

解法二是基于不定积分，我们不妨记 $f(x)=|x|$，经过一次不定积分后的结果为 $f_1(x)$，两次的结果为 $f_2(x)$，也就是 $f_{i+1}(x) = \int f_i (x)$。最后要求的是 $f_n(x)$。不失一般性，我们讨论 $n=2$ 的情况。提取出所有的 $\frac{1}{r_i - l_i}$ 的部分，实际要求的部分其实就是 $\int_{x+l_2}^{x+r_2} \int_{x+l_1}^{x+r_1} f(x) \text{ dx dx}$。其实就是：

$\int_{x+l_2}^{x+r_2} f_1(x+r_1)-f_1(x+l_1) \text{ dx} = f_2(x+r_2+r_1)-f_2(x+l_2+r_1)-f_2(x+l_1+r_2)+f_2(x+l_1+l_2)$。

由于最后要在 $x=0$ 处求值，所以最终这个 $x$ 可以去掉。注意到这个形式和容斥非常类似，式子中 $r$ 出现的次数的奇偶性，决定了 $f_n$ 前面的符号。而由于 $f(x)=|x|$，分正负情况讨论，做 $n$ 次不定积分是很容易实现的。求值复杂度是 $O(\log n)$，整个复杂度可以做到 $O(2^n \log n)$。

Problem C

Upsolved by ultmaster.

题意：给一个无向图，求用最少的路径（可以非简单），覆盖无向图的所有边。

题解：把这个图补成一个有欧拉回路的图，然后找到欧拉回路，在补的虚边的位置把回路断开。由于要输出方案，所以实现起来有一定代码量，但想清楚并不复杂。（吐槽吐在下面）

ultmaster: 这题因为我们没有一个人会欧拉回路，凉了。kblack 提出了任意找圈 + 合并的野鸡解法，然后甩锅给 zerol 写。不仅难写得一批，而且写完发现情况很多根本讨论不完。

然后赛后 kblack 在电梯里提出了加虚边的想法。（其实到此为止才基本是对了）

赛后查了查（其实赛程中也查了，只是没看清楚），发现欧拉回路居然是 $O(E)$ 的，震惊了。。。

吐槽：

• SB 出题人说好了没重边，居然有重边。辣鸡。assert 了半天，一点都不有趣。
• SB 出题人卡时间常数，辣鸡。听说 std 不带 log 的，很感兴趣啊？
• SB 杭电卡空间常数，辣鸡。只给 32 MB 空间。然后一会儿空间换时间，一会儿时间换空间。。。

杭电就是日常这种「就给你 32MB 你必须接受」的态度。都想给杭电捐款买内存条了。。。

Problem D

Solved by ultmaster. 00:16 (+)

题意：给 $[n]$ 每次操作删除一个数和它所有的因数，求先手胜还是后手胜。

题解：好像只有 Yes。证明不详。

Problem E

Solved by zerol. 02:06 (+1)

题意：构造 2000×2000 的 01 矩阵，使得 1 的数量不少于 85000，且不存在 (x1, y1), (x1, y2), (x2, y1), (x2, y2) 同时为 1。

题解：构造 $k^2 \times k^2$ 的矩阵包含 $k^3$ 个 1。首先每列都放 k 个数，将 1~k^2 写成一个 k×k 的数字矩阵 M，每列的 k 个数来自于 M 的每行各一个。k×k 列的选取方法的不同之处在于首项和公差至少有一个不一样（都从 0~k-1 枚举一遍）。正确性依赖于 k 是素数。但是 43^3 不够 85000，所以选取 k=47，取左上角 2000×2000 恰好 1 的个数超过 85000。正确性证明，如果某两列有两个数对应相等，那么这两个数来自于 M 中不同的行，它们的公差是那两个数的距离除以行的距离（模 k 意义下），但根据构造，如果公差一样，那么首项不一样。

Problem F

Upsolved by ultmaster.

题意：棋盘染色。要求至少 $a$ 行 $b$ 列全黑，求方案数。

题解：大量公式预警。

先复习一下容斥：从 Universe 中拿走一些 Bad Events 集合: $E_1, E_2, \ldots, E_n$，求 Good events 的数量 / 权重和。那么，记 $\{E_1,E_2,\ldots,E_n\}$ 的所有子集交为 $F$，那么其实答案就是 $\sum_F w(F) (-1)^{|F|}$。计数的时候 $w(F)=F$。通常情况下 Bad Events 可以解释为「一件事情必须发生，其他事情不管」。注意在求 $E_i \cap E_j$ 的时候一定要考虑清楚这个交是什么意思，有多少个事件。

例如一条长度为 4 的一维的纸带，现在要求不染成全黑的方案数：我们记 $E_i$ 为 $i$ 必须染成黑色（这显然是一个我们不想要的坏事件）。那么好事件的个数就是 $2^4$ (全体，0 个事件的交) 减去 $\sum_{i=1}^4 |E_i| (-1)^{|E_i|} = \binom{4}{1} 2^3 (-1)^4$ 加上 $\sum_{i=1}^4 \sum_{j=i+1}^4 |E_i \cap E_j| (-1)^{|E_i \cap E_j|}$。后面还有一堆东西（两项），就不写了。

回到本问题，我们首先要求的是 $n$ 行 $m$ 列的矩阵没有一行一列是全黑的方案数。这个其实跟上面是同理的。现在有 $n$ 个事件 $A_1,A_2,\ldots,A_n$，$A_i$ 表示第 $i$ 行全黑，$m$ 个事件 $B_1,B_2,\ldots,B_m$，$B_i$ 表示第 $i$ 列全黑。那么显然 $|A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_s} \cap B_{j_1} \cap B_{j_2} \cap \cdots \cap B_{j_t}| = 2 ^{(n-s)(m-t)}$ (因为这些列全黑了，其他的可以乱选)。所以套用容斥公式答案就是 $\sum_{s=0}^n \sum_{t=0}^m (-1)^{s+t} \binom{n}{s} \binom{m}{t} 2 ^{(n-s)(m-t)}$，记为 $f(s,t)$。

答案实际上就是删掉至少 $a$ 行全黑，至少 $b$ 列全黑后，剩下的一个都没有全黑，所以：

[math]\displaystyle{ \begin{align} ans &= \sum_{i=a}^n \sum_{j=b}^m \binom{n}{i}\binom{m}{j} f(n-i, m-j) \\ &=\sum_{i=a}^n \sum_{j=b}^m \binom{n}{i}\binom{m}{j} f(i, j) \\ &=\sum_{i=a}^n \sum_{j=b}^m \binom{n}{i}\binom{m}{j} \sum_{u=0}^i \sum_{v=0}^j (-1)^{u+v} \binom{i}{u} \binom{j}{v} 2 ^{(i-u)(j-v)} \\ &=\sum_{i=a}^n \sum_{j=b}^m \binom{n}{i}\binom{m}{j} (-1)^{i+j} \sum_{u=0}^i \sum_{v=0}^j (-1)^{u+v} \binom{i}{u} \binom{j}{v} 2 ^{uv} \\ &=\sum_{u=0}^{n-a} \sum_{v=0}^{m-b} (-1)^{u+v} 2^{uv} \sum_{i=u}^{n-a} \sum_{j=v}^{m-b} (-1)^{i+j} \binom{n}{i}\binom{m}{j} \binom{i}{u} \binom{j}{v} \\ &=\sum_{u=0}^{n-a} \sum_{v=0}^{m-b} (-1)^{u+v} 2^{uv} \left( \sum_{i=u}^{n-a} (-1)^i \binom{n}{u,i-u,n-i} \right) \left( \sum_{j=v}^{m-b} (-1)^j \binom{m}{v,j-v,m-j} \right) \end{align} }[/math]

到这里为止后面那两块可以预处理，已经可以算了。但是由于此题时限太紧了，所以可能需要进行一定常数优化，比如把后面所带的 $n!$ 和 $m!$ 提出来最后再算。这样应该是能过的（至少我这么过了）。如果还不行的话可能需要进一步化简。

ultmaster：滑稽的是比赛的时候连充斥都没推出来。感觉白学了。所以又复习了一遍。

Problem G

Solved by kblack. 00:39 (+1)

题意：给出排列 $b_i$，对 $a_i$ 区间 $+1$，维护 $\lfloor \frac{a_i}{b_i} \rfloor$，区间求和。

题解：注意到 $b_i$ 是一个排列，每个位置总计最多 $+q$，值会总共最多变化次数是对数级的，故只要线段树记录 $ a_i - (a_i \bmod b_i) $，对于要突变的值暴力维护即可。

Problem J

Solved by zerol. 00:14 (+1)

题意：给一列数，可以花 y 交换相邻两个元素，最后要为每个逆序对付出 x。

题解：显然交换两个相邻元素一定能减少一个逆序对且至多减少一个，所以答案就是 逆序对数量 × min{x,y}。逆序对数量用树状数组或者归并可以求出。