「MCOI-03」数据 官方题解
鏡音リン
·
·
题解
官方题解，较月赛讲评时使用的有较大修改。
题意：给定一个长度为 2n 的 01 串的前 n 个字符，求添加后 n 个字符使得整个 01 串所有长度为 n 的子串的二进制值的方差最小。n\le 1500，数据随机。
对正解没什么帮助的部分分：
$n\le 20$：枚举后 $n$ 个字符计算方差，时间复杂度 $O(n2^n)$，期望得分 $19$ 分。
正解思路：首先推一下方差的式子可以得到一个变形
$$|A|^2S^2=|A|\sum_{x\in A}x^2-(\sum_{x\in A}x)^2$$
那么我们要做的就是最小化右边这个式子。考虑拆贡献，先假设后面的位都是 $0$，那么每一位变成 $1$ 都会对方差构成一个贡献，有两位都是 $1$ 会产生一个联合贡献。
在下面这个表格中，每一列的 $a_i$ 表示左起第 $i+1$ 个长度为 $n$ 子串的二进制值，“总和”表示这 $n+1$ 个数的和。“初始值”那一行代表了后面的位全都是 $0$ 的时候对应数的值，其中 $X$ 表示是输入的 01 串的二进制值，$X_m$ 表示输入的 01 串去掉前 $m$ 位再左移 $m$ 位的二进制值，$S$ 就是这 $n+1$ 个初始值的和。每一行的“第k位”表示左起第 $n+k$ 个字符变成 $1$ 后，对应每一列的增加量。所以，每一列最终的值等于这一列“初始值”那一行的值，加上后面所有为 $1$ 的字符位对应行的值。
| $a_0$ | $a_1$ | $a_2$ | $\dots a_m\dots$ | $a_{n-1}$ | $a_n$ | 总和 | |
| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |
| $X$ | $X_1$ | $X_2$ | $X_m$ | $X_{n-1}$ | $0$ | $S$ | 初始值 |
| | $2^0$ | $2^1$ | $2^{m-1}$ | $2^{n-2}$ | $2^{n-1}$ | $2^n-1$ | 第 $1$ 位 |
| | | $2^0$ | $2^{m-2}$ | $2^{n-3}$ | $2^{n-2}$ | $2^{n-1}-1$ | 第 $2$ 位 |
| | | | $2^{m-k}$ | $2^{n-1-k}$ | $2^{n-k}$ | $2^{n+1-k}-1$ | ...第 $k$ 位... |
| | | | | $2^0$ | $2^1$ | $2^2-1$ | 第 $n-1$ 位 |
| | | | | | $2^0$ | $2^1-1$ | 第 $n$ 位 |
可以看出这个表格是一个斜三角的形式，对角线是 $1$，每向右上角一斜行就翻倍。于是，我们的方差变形式的右侧就等于前 $n+1$ 列的最终值的平方的和，乘以 $n+1$，再减去“总和”一列最终值的平方。把所有平方都打开，整理出只和某一位有关的项和某两位的乘积项，就能整理出每一位变成 $1$ 的单独贡献，和某两位同时变成 $1$ 的联合贡献：（下面省去长长的推式子环节，因为不是题解重点）
第 $k$ 位的单独贡献：
$$(n+1)\sum_{i=k}^n(2\times 2^{i-k}\times (X_m)+2^{2(i-k)})-2\times (2^{n+1-k}-1)\times S-(2^{n+1-k}-1)^2$$
第 $n+1-i,n+1-j,i<j$ 位的联合贡献（注意不是第 $i,j$ 位）：
$$2[\frac{n+1}{3}(2^{i+j}-2^{j-i})-2^{i+j}+2^i+2^j-1]$$
转化成图论模型就是一张图有点权和边权，找一个诱导子图的点权边权和最小。如果点权和边权都任意输入则这个问题是 NPC 的，不能直接做。但是转换成这样可以改成搜索算法，裸的搜索不剪枝计算方法得当也可以达到 $O(2^n)$ 的复杂度，期望得分 $37$。
发现联合贡献全是非负数，可以利用这个性质剪枝。具体方法是，设某一位的单独贡献加上它和之前选过所有位的联合贡献为其当前贡献，如果当前贡献为正，这一位的总贡献一定为正，那么一定不选。如果当前贡献加上它和后面所有位的联合贡献仍然为负，这一位的总贡献一定为负，一定要选。加上剪枝后的搜索很快，开```__int128```就能跑 $n=56$，期望得分 $46$。随便写个高精就能跑更大的范围，但是如果要通过本题，需要一些实现细节上的优化：所有使用高精乘法的地方都可以用二进制位移取代，于是使用二进制压位高精，不需要用高精乘高精。利用二进制状压记录选过的位，那么计算所有联合贡献的和也可以常数次运算得到，不需要枚举每一位。用到的所有操作都是线性复杂度的操作，可以做到搜索单次转移复杂度为 $O(\frac{n}{w})$，也就是常数次高精计算的复杂度。最终要实现的高精大概是：无符号，支持加减法，二进制位移，乘```int```，比大小。
关于复杂度分析：其实我并不会计算这个算法的具体复杂度……实际测试中，dfs 次数大约是 $\frac{n^2}{5}$，dfs 分叉次数大约是 $\frac{n}{4}$。如果按照这个数据，算法的实际复杂度接近 $O(\frac{n^3}{w})$。如果哪位同学证出了严格复杂度，还有非随机数据下的复杂度上界，欢迎来讨论。