题解 CF2180G Balance
JuRuoOIer
·
·
题解
题解 CF2180G Balance
我们的题解确有问题。截至目前，出题人已经修了 7 个锅了，有两个来自本题：[复杂度]()和[式子细节]()。
其他题
题意
给定初始为空的数组 a，要求支持三种操作：
1：删除 a 的第 \lceil\frac{n}{2}\rceil 项。2 x：向 a 的开头、结尾及每相邻两项之间插入 x。3：对于 a 的所有非空子序列 b_1,\dots,b_k 求 \dfrac{\displaystyle\sum_{i=1}^kib_i}{k} 之和，对 10^9+7 取模。
数据范围：多测，t\le 10^4,\sum q\le 10^6。
做法
考虑怎么维护询问的答案。显然通常来说对于所有子序列求的东西拆贡献是比较合适的。
显然最最暴力的求法是枚举每个元素、子序列长度及在子序列中出现的位置，即答案为：
\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^j\dfrac{\text{C}_{i-1}^{k-1}\text{C}_{n-i}^{j-k}ka_i}{j}
然后众所周知根据组合意义，\text{C}_{n}^{m}=\text{C}_{n}^{n-m}。又注意到在题目的限制下，这个数组始终是回文的。所以我们可以分别进行正算和反算，写出答案的两倍的式子：
\begin{aligned}&\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^j\dfrac{\text{C}_{i-1}^{k-1}\text{C}_{n-i}^{j-k}ka_i}{j}+\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^j\dfrac{\text{C}_{n-i}^{j-k}\text{C}_{i-1}^{k-1}(j-k+1)a_i}{j}\\=&\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^j\dfrac{\text{C}_{i-1}^{k-1}\text{C}_{n-i}^{j-k}ka_i}{j}+\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^j\dfrac{\text{C}_{i-1}^{k-1}\text{C}_{n-i}^{j-k}(j-k+1)a_i}{j}\\=&\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^j\dfrac{\text{C}_{i-1}^{k-1}\text{C}_{n-i}^{j-k}(j+1)a_i}{j}\\=&\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^j\text{C}_{i-1}^{k-1}\text{C}_{n-i}^{j-k}a_i+\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^j\dfrac{\text{C}_{i-1}^{k-1}\text{C}_{n-i}^{j-k}a_i}{j}\end{aligned}
我们发现，加号前面是所有子序列元素和的和，后面是所有子序列平均值的和。所以首先加号前面的部分可以直接写成 2^{n-1}\sum a_i。
然后考虑加号后面的部分。当长度 j 定下来的时候，利用范德蒙恒等式 \text{C}_a^b\text{C}_c^d=\text{C}_{a+b}^{c+d} 容易表示出一个数 a_i 的贡献为 \dfrac{\text{C}_{i-1}^{k-1}\text{C}_{n-i}^{j-k}a_i}{j}=\dfrac{\text{C}_{n-1}^{j-1}a_i}{j}，加上枚举 a_i 和 j 的过程，得到这部分贡献为
\begin{aligned}&\sum_{i=1}^n\sum_{j=1}^n\dfrac{\text{C}_{n-1}^{j-1}a_i}{j}\\=&\sum_{i=1}^na_i\sum_{j=1}^n\dfrac{\text{C}_{n-1}^{j-1}}{j}\\=&\sum_{i=1}^na_i\sum_{j=1}^n\dfrac{(n-1)!}{j(j-1)!(n-j)!}\\=&\sum_{i=1}^na_i\sum_{j=1}^n\dfrac{n!}{nj!(n-j)!}\\=&\sum_{i=1}^na_i\dfrac{\displaystyle\sum_{j=1}^n\text{C}_{n}^{j}}{n}\end{aligned}
由二项式定理，取 a=b=1 时有 \displaystyle\sum_{j=\mathbf{0}}^n\text{C}_{n}^{j}=2^n，所以上式等于 \displaystyle\sum_{i=1}^na_i\dfrac{2^n-1}{n}。
到这里，我们已经把贡献化成了仅与 n 和 \sum a_i 相关的式子，所以我们需要维护的就是这两个值。n 显然是容易维护的，而有了 n 后插入操作的 \sum a_i 也容易维护。所以现在我们需要找到删除操作删掉的到底是谁。
考虑一次插入操作。插入后数组的长度必然变为奇数（这个可以通过分讨插入前的奇偶性证明，这里不展开）。此时，
- 如果插入前长度就是奇数，那么下次删除的时候还是删除原数组中间的位置，然后再往下两次删除两个 x，再往下就规约到形如
xoox 的状态，其中 x 表示新插入的 x，而两个 o 则是原来中间位置两侧的两个数。
- 如果插入前长度是偶数，那么下次删除的时候删除的是 x，然后删除原数组中间元素，再往下也规约到形如
xoox 的状态。
从 xoox 的状态出发，我们考虑对于每次插入操作，维护其状态 0/1/2/3，其中插入的时候如果当前长度为偶数则插入 1，否则插入 3。然后删除的时候，从后往前扫每个插入操作，如果某个操作是状态是 0/1 则删掉的就是这个数，将其加 1 并模 4 后停止遍历；反之则将其加 1 并模 4 后继续遍历。
这个过程的均摊复杂度是 O(1) 的。证明考虑维护从中间开始长度为 q 的窗口，这是此时极端情况下能删掉的所有元素。每次插入时必然会将窗口内至少一半的元素替换成操作时间为 O(1) 的 x，而原有部分的时间代价会加一，但含量会减半。所以最终倒数第 k 个加入的二操作在窗口中的含量应该是 \dfrac{q}{2^k}，即该次插入操作贡献的总时间代价是 k\dfrac{q}{2^k}，对其求和的值为无限接近 2q，方法是注意到 S-\frac{1}{2}S=\sum_k\frac{1}{2^k}=1。
所以总复杂度应该是 O(q \log V)。不知道官解里的 \log q 哪来的，可能是算上了快速幂的时间，但快速幂也不是 \log q 的吧（虽然 \log V 和 \log q 没啥区别）……
（upd：出题人把复杂度改过来了）