2021牛客暑期多校第七场

排名	当场过题数	至今过题数	总题数
56/1294	3	11	11

A

upsolved by JJLeo

题意

给定 \(n\) 个点的完全图，每条边有一个权值，定义一个边集是好的当且仅当它将 \(n\) 个点连通，一个边集的权值是所有边权的积乘以边集大小，求所有好边集的权值和。(\(1 \le n \le 20\))

题解

本题需要利用集合幂级数的相关知识解决。

设集合大小为 \(n\)，则

\[ F(x)= \sum _{i=0} ^ {2^n-1}f_ix^i \]

称作集合幂级数，这里的 \(i\) 用二进制表示后可以代表一个集合，\(f_i\) 代表集合 \(i\) 对应的系数。

那么 FWT 的三种卷积看看作是两个集合幂级数在以一种特殊的规则在卷。

子集卷积可以看作是二元幂级数的运算，设

\[ \begin{aligned} F(x,y)=\sum \limits _{i=0} ^ {2^n-1}f_ix^iy^{\operatorname{popcount}(i)} \newline G(x,y)=\sum \limits _{i=0} ^ {2^n-1}g_ix^iy^{\operatorname{popcount}(i)} \end{aligned} \]

则 \(x\) 卷积是 OR 卷积，而 \(y\) 卷积是正常的加法卷积，也即：

\[ \begin{aligned} H(x,y)=&F(x,y)G(x,y) \newline =&\sum_{i=0}^{2^n-1}\sum_{j=0}^{n}\sum_{a=0}^{2^n-1}\sum_{b=0}^{2^n-1}\sum_{c=0}^{n}\sum_{d=0}^{n}[a \cup b=i][c+d=j]\left[x^ay^c\right]F(x,y)\left[x^by^d\right]G(x,y)x^iy^j \newline =&\sum_{j=0}^{n}y^j\sum_{c=0}^j\left[y^c\right]F(x,y)\left[y^{j-c}\right]G(x,y) \end{aligned} \]

这也就是子集卷积做法的原理，直接做复杂度是 \(O\left(n^22^{2n}\right)\)，但是我们可以加速 \(x\) 卷积的过程，利用 FWT 后的可加性，对每个 \(\left[y^j\right]F(x,y)\) 和 \(\left[y^j\right]G(x,y)\) (也就是每一行) 先做 FWT，之后就可以用 \(O\left(2^n\right)\) 完成一次点乘，将每个 \(\left[y^j\right]H(x,y)\) (也就是每一行) 的全部点值加起来后，做一次 IFWT 即可。

需要注意的是，\(x\) 个集合的元素并上 \(y\) 个集合的元素后有 \(x+y\) 个元素当且仅当它们不交，利用这条性质我们只能确保所有 \(\left[x^iy^{\operatorname{popcount}(i)}\right]H(x,y)\) 是对的，当然我们也只需要用到这些值。

既然第二维可以做加法卷积，那也可以做 \(\exp\) 和 \(\ln\)，其拥有同样的组合意义，只不过是在子集卷积意义下的，我们以 \(\exp\) 为例：

\[ G(x,y)=\exp F(x,y)-1=\sum_{i=1}^{\infty} \frac{F^i(x,y)}{i!} \]

这里幂级数之间的运算就是上面提到的子集卷积。

对于固定的 \(\left[y^j\right]G(x,y)\)，相当于数个 \(\left[y^k\right]F(x,y)\) (遵循 \(\exp\) 的定义) 按照 OR 卷积起来，那么和算子集卷积一样，对每个 \(\left[y^j\right]F(x,y)\) 先做 FWT，这样每一列之间就是独立的了。

单独看每一列，相当于做 \(y\) 这个变量的加法卷积 \(\exp\)，\(n\) 一般不超过 \(20\)，套多项式板子没有必要，可以用 \(\exp\) 的泰勒展开及求导得到一个 \(O\left(n^2\right)\) 做法，不受模数限制：

\[ \begin{aligned} G(x)&=\exp F(x)-1 \newline \frac{\text dG(x)}{\text dx}&=\frac{\text dF(x)}{\text dx}\exp F(x) \newline \frac{\text dG(x)}{\text dx}&=\frac{\text dF(x)}{\text dx}(G(x)+1) \newline \frac{\text dG(x)}{\text dx}&=\frac{\text dF(x)}{\text dx}+\frac{\text dF(x)}{\text dx}G(x) \newline (i+1)g_{i+1}&=(i+1)f_{i+1}+\sum_{j=0}^i (j+1)f_{j+1}g_{i-j} \newline g_{i}&=f_{i}+\frac{1}{i}\sum_{j=0}^{i-1} (j+1)f_{j+1}g_{i-1-j} \newline \end{aligned} \]

这样我们就可以对每列 \(O\left(n^2\right)\) 求出 \(\exp\) 后的结果，最后对每个 \(\left[y^j\right]G(x,y)\) 做 IFWT 即可。

\(\ln\) 是相同的，仅作公式推导：

\[ \begin{aligned} G(x)&=\ln(F(x)+1) \newline \frac{\text dG(x)}{\text dx}&=\frac{\text dF(x)}{\text dx}\frac{1}{F(x)+1} \newline \frac{\text dG(x)}{\text dx}F(x)+\frac{\text dG(x)}{\text dx}&=\frac{\text dF(x)}{\text dx} \newline \frac{\text dG(x)}{\text dx}&=\frac{\text dF(x)}{\text dx}-\frac{\text dG(x)}{\text dx}F(x) \newline (i+1)g_{i+1}&=(i+1)f_{i+1}-\sum_{j=0}^i(j+1)g_{j+1}f_{i-j} \newline g_i&=f_i-\frac{1}{i}\sum_{j=0}^{i-1}(j+1)g_{j+1}f_{i-1-j} \end{aligned} \]

先不考虑乘以边集大小，设 \(g_i\) 为边集经过的点在集合 \(i\) 中的所有边集权值乘积之和，\(f_i\) 为边集经过的点在集合 \(i\) 中且 \(i\) 连通的所有边集权值乘积之和，设：

\[ \begin{aligned} F(x,y)=\sum \limits _{i=0} ^ {2^n-1}f_ix^iy^{\operatorname{popcount}(i)} \newline G(x,y)=\sum \limits _{i=0} ^ {2^n-1}g_ix^iy^{\operatorname{popcount}(i)} \end{aligned} \]

则有：

\[ \begin{aligned} G(x,y)&=\exp F(x,y)-1 \newline F(x,y)&=\ln(G(x,y)+1) \end{aligned} \]

枚举每条边，设其边权为 \(w\)，将所有能选这条边的点集 \(i\) 的 \(g_i\) 变为 \(g_i+wg_i\)。这样可以在 \(O(n^22^n)\) 的时间内求出全部 \(g_i\)，之后用集合幂级数 \(\ln\) 即可求得所有 \(f_i\)，最终答案即为 \(f_{2^n-1}\)。

再考虑乘以边集大小，相当于把每个数换成一个多项式 \(f(x)=\sum \limits _{i=0} ^ \infty a_ix^i\)，每项系数为边集大小是 \(i\) 的权值乘积和，最终答案即为 \(\dfrac{\text d}{\text dx}f(1)=\sum \limits _{i=0} ^ \infty a_ii\)。

我们只需维护 \(f(1)\) 和 \(\dfrac{\text d}{\text dx}f(1)\) 即可，两个多项式 \(f(x)\) 和 \(g(x)\) 相加，两者变为：

\[ \left(f(1)+g(1),\frac{\text d}{\text dx}f(1)+\frac{\text d}{\text dx}g(1)\right) \]

两个多项式 \(f(x)\) 和 \(g(x)\) 相乘，两者变为：

\[ \left(f(1)g(1),g(1)\frac{\text d}{\text dx}f(1)+f(1)\frac{\text d}{\text dx}g(1)\right) \]

使用一个二元组结构体重载运算符并取代 int 即可，注意求 \(g_i\) 时乘以 \(w\) 也应改成 \(g_i\) 乘以一个多项式 \((1+wx)\)，因此二元组为 \(\left(1+w,w\right)\)。

总时间复杂度为 \(O\left(n^2 2^n\right)\)。

B

upsolved by JJLeo

题意

给定一个两个序列 \(a_1,a_2,\ldots a_n\) 和 \(b_1,b_2,\ldots b_n\)，有 \(q\) 次下列三种操作之一：

• 给定 \(l,r\)，从位置 \(l\) 开始，不断进行下列操作：

设当前位于 \(i\)，找到最小的 \(j\) 满足 \(a_j\ge a_i\) 且 \(j>i\)，如果 \(j \le r\) 则移动到 \(j\) ，否则终止。

设经过了 \(p_1,p_2,\ldots,p_m\)，求 \(\sum \limits _{i=1} ^{m-1} [b_{p_i} \not \equiv b_{p_{i+1}} \pmod 2]\)。

• 单点修改 \(a_i\)。

• 区间对 \(b_i\) 取反。

(\(1 \le n \le 2 \times 10^5\)，\(0 \le a_i \le 10^9\)，\(0 \le b_i \le 1\))

题解

赛时做法是分块，对每个块维护以下两个东西：

• 递增的单调栈，就是将所有 \(a_j \le a_i \land j >i\) 的 \(a_j\) 扔掉。
• 从每个位置进来，会从哪个位置出去，及其对应的代价。

设块长为 \(B\)，这两个东西对每个块都可以 \(O(B)\) 维护：

• 第一个正着扫一遍看是否比末尾大即可，若是则加入。
• 第二个倒着扫一遍做单调栈即可。

对于单点 \(a_i\) 修改直接重构这块，对于区间对 \(b_i\) 取反则整块打标记，边角暴力重构。注意到整块如果全部取反那么从每个位置出去的代价是不变的，因此不用改。

查询时块内 \(O(1)\) 跳，块间利用递增的单调栈二分找到进入的位置，加上这一次答案，再跳即可。

修改复杂度为 \(O(B)\)，询问复杂度为 \(O\left(\dfrac{n}{B}\log n\right)\)，取 \(B=\sqrt{n \log n}\)，即可得到 \(O(q\sqrt {n \log n})\) 的复杂度。

比赛时脑瘫去写了值域分块试图消去 \(O(\log n)\)，结果复杂度假了，反而因为辣鸡 vector 慢的要死。

忘记修改和查询有一个不带 \(O(\log n)\)，块大小不对直接裂开，最后块大小对了但是维护递增单调栈的时候少写了个 a[]，没调出来寄了，只能我说是脑瘫。

正解是 log-update 的线段树，有时间补。

C

upsolved by 2sozx

题意

对于一个数 \(x\) 每次操作后能变为 \(x + \operatorname{popcount}(x)\) ，\(10^7\) 个询问，每次询问 \(a, b\) ，问对 \(a\) 进行无限次操作后，第一个大于等于 \(b\) 的数是多少，最后一起输出。 \(1\le a < b < 2^{64}\)

题解

首先我们可以发现一个显然的结论，每次移动不超过 \(64\) 次，因此我们可以将 \(x\) 分解，设其为 \(x = M \times 2^6 + m\)

首先我们定义一个数组 \(f_{i, j, k}\) 表示第 \(0\sim i - 1\) 位为 \(0\)，\(m\) 为 \(j\) ，\(i\sim 57\) 位的 \(\operatorname{popcount}\) 为 \(k\) ，经过很多次移动后 \(i\sim 57\) 位发生变化后 \(m\) 最小是多少，这里将最后 \(6\) 位与前面的 \(58\) 位分开考虑。通过这个定义我们可以很容易的想出来这个 \(f\) 的转移。详细的说就是 \(i \not= 0\) 时，相当于 \(i - 1\) 位变化两次；\(i = 0\) 是让 \(m\) 进位即可。

\[ f_{i,j,k} = \begin{cases} j + \operatorname{popcount}(j) + k - 64\quad i = 0 \wedge j + \operatorname{popcount}(j) + k \ge 64\newline f_{i, j + \operatorname{popcount}(j) + k,k}\quad i = 0 \wedge j + \operatorname{popcount}(j) + k < 64\newline f_{i - 1, f_{i - 1, j, k}, k + 1} \quad i \not= 0 \end{cases} \]

转移的复杂度是 \(O(64^3)\) 的。有了这个东西我们考虑如何用 \(f\) 来计算答案。

考虑 \(a, b\) 的二进制表示，我们可以从地位到高位转移 \(a\) ，如果从这位开始，\(a,b\) 到最高位的二进制表示完全相同，那么我们就可以用 \(f\) 数组从这位向低位让 \(a\) 始终贴着 \(b\) 的上界即可。如果到最高位的二进制表示不同，那么为了要用上我们的 \(f\) 数组，需要让这位的 \(a\) 变成 \(0\) ，然后继续考虑更高的一位。

这个做法复杂度是 \(O(64 \times 2\times q)\) 的，\(q\) 是询问次数，但是出题人不想让这个做法过去，因此我们还得优化下算法。

考虑我们处理 \(f\) 数组的复杂度只有 \(O(64^3)\) ，我们还可以用更多的时间处理更多的东西，考虑将前面 \(58\) 位分块，块大小为 \(B\)，定义一个新的数组 \(g_{i,j,k,s,l}\) 表示考虑到了第 \(i\) 块，\(m = j\) ，\(i + 1\) 块到 \(\lfloor\frac{58}{B}\rfloor\) 的 \(\operatorname{popcount}\) 为 \(k\) ，第 \(i\) 块的状态为 \(s\) ，转移到第 \(i\) 块状态为 \(l\) 后 \(m\) 最小是多少，这个转移可以用之前求过的\(f\) 数组求，预处理的复杂度就是 \(O(\lfloor\frac{58}{B}\rfloor\times2^B\times 2^B\times 58\times64)\)

然后用和之前做法类似的想法就可以用 \(g\) 数组求每一次的答案了，复杂度为 \(O(q\times\lfloor\frac{58}{B}\rfloor)\) ，大概取 \(B = 6\) 最优。

然而实际测试你会发现效率和暴力差不多，经过实际测试会发现这个做法常数巨大，一点一点测会发现每次调用 \(g\) 数组常数巨大，因为是个五维数组，而且每一维没有什么移动的性质，导致他慢的要死，考虑优化一下这个常数。观察我们的转移，我们会发现，对于同一块，我们有三种操作模式：

• 一种是从此刻块的状态 \(s\) 变为 \(0\) 并且前面进位
• 从此刻状态为 \(0\) 变为 \(b\) 再这个块的状态
• 普通的转移

我们会发现前两种东西可以用一个四维数组存下，第三种情况其实只会发生一次，这样我们就卡掉了很多很多的常数。

对于空间来说，我们的数组需要开 char，因为每个数组答案都不超过 \(64\) ，而且开 int 就会爆空间。

这题真是nt卡常，卡了至少一天半的常数，还是看了又个人过了的代码发现五维数组比四维常数大了不知道多少倍，无限乱卡，本地跑的比过的人快了交上去还是T，真是离谱。

🐍有个贼优的做法，那个五维数组小了不少。

D

upsolved by JJLeo

题意

求解 \(n\) 阶元素为 \(d\) 次多项式的行列式。(\(0 \le n,nd \le 500\)，\(n \ge 1\))

题解

首先构造如下 \(n(d+1) \times n(d+1)\) 的矩阵，将其写为每块 \(n\times n\) 的 \((d+1)\times(d+1)\) 的分块矩阵：

\[ B=\begin{pmatrix} xI_n & -I_n & 0 & \cdots & 0 & 0 \newline 0 & xI_n & -I_n & \cdots & 0 & 0 \newline \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \newline 0 & 0 & 0 & \cdots & xI_n & -I_n \newline M_0 & M_1 & M_2 & \cdots & M_{d-1} & M_d \end{pmatrix} \]

其中 \(M_i\) 是 \(x^i\) 的系数矩阵，最终要求解的行列式是 \(\left|\sum \limits _{i=0}^d x^iM_i\right|\)。

通过初等列变换，易得上述这个分块矩阵的行列式就是我们要求的行列式，具体来说，按顺序将第 \(i\) 列乘以 \(x\) 加到第 \(i-1\) 列，其中 \(i=n,n-1,\ldots,2\)，最终该分块矩阵变为如下形式：

\[ B’=\begin{pmatrix} 0 & -I_n & 0 & \cdots & 0 & 0 \newline 0 & 0 & -I_n & \cdots & 0 & 0 \newline \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \newline 0 & 0 & 0 & \cdots & 0 & -I_n \newline \sum \limits _{i=0}^d x^iM_i & \sum \limits _{i=1}^d x^{i-1}M_i & \sum \limits _{i=2}^d x^{i-2}M_i & \cdots & M_{d-1}+xM_d & M_d \end{pmatrix} \]

其行列式按第 \(1\) 列展开得到 \({(-1)}^{d+2}\left|\sum \limits _{i=0}^d x^iM_i\right|{|-I_n|}^d=\left|\sum \limits _{i=0}^d x^iM_i\right|\)。

我们考虑如何求出 \(|B|\)，假设 \(M_d=I_n\)，我们将第 \(d\) 行加到第 \(d+1\) 行上，得到：

\[ B''=\begin{pmatrix} xI_n & -I_n & 0 & \cdots & 0 & 0 \newline 0 & xI_n & -I_n & \cdots & 0 & 0 \newline \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \newline 0 & 0 & 0 & \cdots & xI_n & -I_n \newline M_0 & M_1 & M_2 & \cdots & M_{d-1}+xI_n & 0 \end{pmatrix} \]

其行列式按第 \(d+1\) 列展开得到：

\[ \begin{vmatrix} xI_n & -I_n & 0 & \cdots & 0 & 0\newline 0 & xI_n & -I_n & \cdots & 0 & 0\newline \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \newline 0 & 0 & 0 & \cdots & xI_n & -I_n \newline M_0 & M_1 & M_2 & \cdots & M_{d-2} & M_{d-1}+xI_n \end{vmatrix} \]

这是一个形如 \(|A+xI|\) 的行列式，可以用特征多项式的方法 \(O\left((nd)^3\right)\) 求解。

我们只需将 \(M_d\) 转化为 \(I_n\)，考虑对 \(\left|\sum \limits _{i=0}^d x^iM_i\right|\) 进行初等行列变换，将其变为 \(C(x)\left|x^dI_n+\sum \limits _{i=0}^{d-1} x^iM'_i\right|\) 的形式：

首先使用初等行变换对每一列正常消元，将 \(d\) 次项消成只有对角线上的系数为 \(1\) 其它均为 \(0\)。

但 \(M_d\) 不一定满秩，因此可能出现消到第 \(i\) 列时，所有 \(j \ge i\) 行的 \(d\) 次项系数均为 \(0\) 的情况，我们可以使用如下方法解决这一问题：

• 此时前 \(i-1\) 列都只有对角线上 \(d\) 次项系数为 \(1\) 其它均为 \(0\)，利用初等列变换将第 \(i\) 列所有 \(j<i\) 行的 \(d\) 次项系数全部消为 \(0\)。
• 接着对第 \(i\) 列乘以 \(x\)，则最终将行列式除以 \(x\)，此时如果存在 \(j \ge i\) 行的 \(d\) 次项系数不为 \(0\)，将其交换后即可正常消元；否则重复第一步。

我们每进行一次操作，最终行列式就会除以一个 \(x\)，由于每次进行后行列式的次数不超过 \(nd\) 且不是分式，如果进行了 \(nd+1\) 次，那么最终行列式必然为 \(0\)。

该操作一次的时间复杂度是 \(O\left(n^2d\right)\) 的，最多进行 \(O(nd)\) 次，因此复杂度不超过 \(O\left(n^3d^2\right)\)。

综上，时间复杂度为 \(O\left((nd)^3\right)\)。需要注意用一维数组模拟三维数组会快很多，利用空间连续性减少 cache miss，不要用辣鸡 vector，否则在 \(d \le 1\) 时直接卡飞。

E

upsolved by JJLeo

题意

一个只能拿特定石子数量的 nim 游戏，每堆石子初始数量为 \([l_i,r_i]\)，求先手必胜的方案数。(\(1 \le n \le 10^6\)，\(1 \le l_i \le r_i \le 10^5\))

题解

可以打表得出 SG 函数值不超过 \(230\)。

首先开 \(231\) 个 bitset，求出 \(\left[0,10^5\right]\) 石子数的 SG 函数值，设 \(b_{i,j}\) 为 \(j\) 个石子对应的节点有没有指向 SG 函数值为 \(i\) 的出边，从小到大遍历 \(j\) 并维护每个 \(b_{i,j}\) 即可 \(O(231)\) 求出每个点的 SG 函数。

考虑如何维护 \(b_{i,j}\)，设现在确定了 \(j\) 个石子的 SG 函数为 \(s\)，那么只需将所有 \(b_{s,k}\) 变为 \(1\)，其中 \(k\) 是能通过一次拿石子到达 \(j\) 的状态，先求出一个 bitset \(B\)，\(B_i=1\) 当且仅当每次可以拿 \(i\) 个石子，那么只需让 \(b_s := b_s\mid (B<<j)\) 即可 。设 \(m=10^5\)，这一部分总复杂度为 \(O\left(231m+\dfrac{m^2}{w}\right)\)。

接下来相当于求每个位置选择 SG 函数后异或起来非 \(0\) 的方案数，设 \(k=8\)，全部做 FWT 后卷起来的复杂度为 \(O(nk2^k)\)，会 T。考虑到每堆石子可选数量是一个连续区间，利用 FWT 的本质，可以用前缀和优化：

\[ \operatorname{FWT}(A)_i=\sum_{j=0}^{2^k-1}{(-1)}^{\operatorname{popcount}(i\&j)}A_j \]

我们可以直接利用这个公式求出一个位置增加 \(1\) 对整个 FWT 每个位置的贡献，也可以偷懒对只有这一个位置是 \(1\) 其它全是 \(0\) 的序列做一次 FWT (这样预处理会多个 \(k\) 的复杂度，不过无所谓)，对每个位置做前缀和，对于每堆石子即可 \(O(2^k)\) 得到其 FWT 数组，乘起来做一次 IFWT 即可，这样总时间复杂度为 \(O(2^{2k}+n2^k)\)。

F

solved by 2sozx JJLeo

题意

两棵 \(n\) 个节点的有根树，选一个最大点集，其在第一棵树上是从上到下的一个连续链，第二棵树上任意两点不能有祖先关系。(\(1 \le n \le 3 \times 10^5\))

题解

可能是这题 CF1528C 读错题后的版本（x

赛时做法是 dfs 第一棵树，只考虑第一棵树上 dfs 的该点及其所有祖先。每次新增一个点，在第二棵树的子树和其父亲找到被考虑点中深度最浅的点，并用一个 multiset 维护所有考虑点所对应的这个点的 dfn 序，这样就可以得到以该点为第一棵树上最深点的答案，回溯时记得将其从 multiset 删掉即可。这样复杂度是 \(O(n \log ^2 n)\)，常数小卡过去了。

一种 \(O(n \log n)\) 的做法，利用一个结论：两个点互不为祖先当且仅当它们子树对应的 dfn 序区间互不相交。

这样我们还是 dfs 第一颗树，做树上的双指针，对于每个点覆盖其第二棵树子树对应的 dfn 序区间，如果有一个区间被覆盖多次则不行。记录一下上端点位置，回溯时移动回去即可。

G

upsolved by Bazoka13

题意

给定 \(R\) 和二维平面上 \(n\) 个点，每个点的权值是一个 \(Z\) 维向量，求所有距离不超过 \(R\) 的不同无序点对的权值内积和，数据给定种子随机生成，时限 \(8\) 秒。(\(1 \le n \le 10^5\)，\(Z=120\))

题解

直接 KDTree 暴力复杂度大约是 \(O\left(n\sqrt nZ\right)\)，本地跑了 \(70\) 秒。

使用以下四个剪枝即可卡常通过：

• 因为没有修改，用线段树代替平衡树，这样每次合并左右子树只需一次，而平衡树需要合并左右子树和自己需要两次。
• 剪枝时返回的零向量没必要再合并，可以进行特判。
• 两个节点之间的答案不要算两次，对第 \(i\) 个节点只考虑节点 \([i+1,n]\)。每次查询完点 \(i\) 后，对线段树进行单点修改，将点 \(i\) 标记，如果一个区间所有点都被标记那么剪枝退出。
• 预处理子集和，线段树构建过程中，当区间节点少于 \(B\) 时，停止递归，\(O\left(2^B\right)\) 预处理该区间所有子集的向量和。查询到该节点时 \(O(B)\) 判断要不要每个节点，之后 \(O(1)\) 获取其子集和。

取 \(B=4,5,6,7\) 可以通过，\(B\) 再大空间就不够了。

J

upsolved by JJLeo

题意

\(n\) 个点 \(m\) 条边的有向图，对于把 \(k\) 写到最内层循环的假 floyd 算法，有多少点对的最短距离是正确的，边权均不为 \(0\)。(\(1 \le n \le 2000\)，\(0 \le m \le 5000\))

题解

首先跑 \(n\) 次 dijkstra 得到任意两点间的最短路。

之后按照假算法先 \(i\) 后 \(j\) 的枚举顺序，依次确定 \(d_{i,j}\) 是否正确。\(d_{i,j}\) 正确当且仅当：

• 存在一条边 \(i \to j\) 其权值就是最短路。
• 枚举到 \(i,j\) 时，存在点 \(k\) 在 \(i\) 到 \(j\) 的最短路上，且 \(d_{i,k}\) 和 \(d_{k,j}\) 都是正确的。

第一个情况可以直接处理出来，对于第二种情况，我们维护 \(2n\) 个 bitset \(a_i,b_i,c_i\)，\(a_{i,j}=1\) 当且仅当 \(d_{i,j}\) 是对的，\(b_{i,j}=1\) 当且仅当 \(d_{j,i}\) 是对的。此外，每遍历到一个 \(i\)，我们再维护 \(n\) 个 bitset \(c_j\)，\(c_{j,k}=1\) 当且仅当 \(k\) 在 \(i\) 到 \(j\) 的最短路上。那么第二种情况等价于 \(a_i,b_j,c_j\) 三者交集不为空。

对于 \(a\) 和 \(b\) 直接求出每个点对后改为 \(1\) 即可，对于 \(c\) 的维护我们将每个点 \(j\) 按照到 \(i\) 的距离从小到大排序依次遍历，对于点 \(j\) 的每条入边 \(k \to j\)，如果其是最短路上的边，那么所有 \(i\) 到 \(k\) 最短路上的点也都在 \(i\) 到 \(j\) 的最短路上，将 \(c_{j}\) 并上 \(c_{k}\) 即可，最后还要令 \(c_{j,j}=1\)。

总时间复杂度为 \(O\left(nm \log m+\dfrac{n^2m}{w}\right)\)。

题解还有一个 \(w=0\) 也可行的做法，没懂，同时也没懂为什么 \(w=0\) 这个做法不可行。

K

upsolved by JJLeo

题意

给定长度为 \(n\) 的序列，\(q\) 次询问，每次给定 \(k,l,r\)，对于区间 \([l,r]\)，每次可以选择一个区间 \(+1\) 或 \(-1\)，求最少次数将所有数变为 \(0\)，所有运算都在模 \(k\) 意义下，序列所有数小于所有 \(k\)。(\(1 \le n \le 2 \times 10^5\)，\(1 \le q \le 10^5\))

题解

考虑单组询问怎么做。对原序列差分，第一个数不变，设为 \(b_1,b_2,\ldots,b_n\)，最终还是要让所有数变为 \(0\)，那么每次操作 \([l,r]\) 等价于：

• \(r \ne n\)，那么 \(b_l,b_{r+1}\) 一个加 \(1\) 一个减 \(1\)。
• \(r=n\)，那么 \(b_l\) 加 \(1\) 或减 \(1\)。

那么问题转化为选择一些数让其加 \(1\)，剩下数减 \(1\)，设有 \(x\) 次加 \(1\) 和 \(y\) 次减 \(1\)，那么要最小化 \(\max(x,y)\)。

注意到序列差分后有负数，模意义下要先让其 \(+k\)。现在所有数都是 \([0,k)\) 了，一个数 \(x\) 加 \(1\) 需要 \(k-x\) 次，减 \(1\) 需要 \(x\) 次，显然排序后前面一段都减 \(1\)，后面都加 \(1\)。

设需要加 \(1\) 的数的和为 \(A\)，个数为 \(x\)，所有数总和为 \(B\)，那么答案即为 \(\max(B-A,kx-A)\)，当 \(x=\left\lfloor\dfrac{B}{k}\right\rfloor\) 或 \(x=\left\lfloor\dfrac{B}{k}\right\rfloor+1\) 时取得最小值。

对于多组询问，\(k\) 和选取区间都不同，用两个主席树分别存差分后的正数和负数，可以 \(O(\log n)\) 获取区间大于某个数的个数和元素和。\(B\) 可以简单的获得，从而可以获得 \(x\) 的值，因此二分 \(A\) 的值，即可得到 \(\max(B-A,kx-A)\)，对两个 \(x\) 得到的值取 \(\min\) 即可。

需要注意我们默认第一个数不变，但预处理时 \(b_l=a_l-a_{l-1}\)，因此差分只考虑 \([l+1,r]\) 的部分，\(a_l\) 最后加入特判即可。

记录

这场属于是逆了大天了，补题都难顶

0h：开局俩签到，但是一个corner case没判，WA了一发，看F好像是之前做过的原题，MJX和ZYF开想，CSK抄KDT板子

1h：听后面数理逻辑说 \(O(\log ^2 n)\) 不知道啥算法被卡了，心慌慌，但是还是莽了一发F，过了(x。测了测KDT的速度，跑了70s，很好，完全过不去。

2h~3h：挂！3h最后想了个B的分块做法，但是很麻烦，只能慢慢写。

4h：写着写着发现咋写都得二分，值域分块就没用了，甚至无限扩大常数，然后爆T。到最后改改块大小变成WA了。

after end：ZYF B判断错了，寄！块大小应该直接变成 \(\sqrt{n\log n}\) ，不然复杂度不对。

总结

Dirt