2020-05-23 22:04 已编辑算法工程师

关注

【题解】VMware校园挑战赛-牛客挑战赛40

由于出题人和验题人姿势比较差，E题标解的思路比较繁琐且复杂度不够优秀，能处理的数据范围比较小，导致最终的结果是过了很多相对简单的低于 $O(nq\log n)$ 的做法，导致这道题的实际难度低于预期。给各位大爷添堵了。感谢大爷们优秀做法，受教了。希望大家喜欢其它的题目。

A

将 $m$ 写为 $a\sqrt b$ （ $b$ 为无平方因子数）的形式，则合法的解中，每个 $\sqrt {x_i}$ 必然是 $u_i\sqrt b$ 的形式，且满足

$u_1 + u_2 + \cdots + u_n = a$

问题等价于求上述方程的本质不同解数，可以DP解决。

B

将一个数字的 $64$ 位分成 $4$ 段，每段 $16$ 位，因为最多有 $3$ 位不同，故至少有一段完全相同，所以只需要枚举被询问数字的 $4$ 段，在与这个数字当前枚举到的段相同的数字中查询是否有解即可。因为数字随机，约有 $2^{20}$ 个数字，故每一块下期望检索到 $2^{20-16}=2^4=16$ 个数字，总复杂度为 $O(4 \times 16 \times q)$ 。

C

考虑两个串 $s_1s_2\cdots s_n$ ， $t_1t_2\cdots t_n$ ，如果他们中的0的个数相同，那么可以从 $s$ 变到 $t$ 。

如何计算交换步数呢？考虑 $s,t$ 长度为 $p$ 的前缀 $\text{prefix}(s,p)=s_1s_2\cdots s_p,\text{prefix}(t,p)=t_1t_2\cdots t_p$ ，假设此时 $\text{prefix}(s,p)$ 中的 $0$ 的个数为 $cnt_1$ ， $\text{prefix}(t,p)$ 中 $0$ 的个数为 $cnt_2$ ，且 $cnt_1 > cnt_2$ ，则此时贡献了 $cnt_1-cnt_2$ 步。对每个前缀都计算出其贡献最后累加就得到了 $f(s,t)$ 。

在这个算法上套一个数位DP即可，总复杂度可做到 $O(n^2)$

D

对每个类型的基站维护一个set，存有哪些连续线段。再维护一个全局的set，存储三元组 $(l_i,r_i,type_i)$ 。每次覆盖操作时，在全局的set里找到相应线段，然后在对应类型基站的set中找相应线段，进行修改。这样，就可以保证全局set中的线段每次操作要么减少要么只会增加 $2$ 个。对于替换操作，作启发式合并即可。对于查询操作，二分即可。

E

这是出题人和验题人的原(la)始(ji)想法：由于修改一个节点会导致与之相连的所有的边发生改变，因此需要考虑修改不过于影响效率的做法。对于任何一条路径，无论修改哪个点，都最多影响该条路径上的两条边。因此可以考虑在欧拉序上进行带修改莫队。将每一条路径可以对应到欧拉序列上的一个区间，移动区间每移动一位需要计算一次边权。在按照时间修改时由于每次修改最多有两条边在当前路径上，可以记录下当前与每个点相连的边有哪几条对当前询问有贡献，因此一次修改最多需要计算两次边权。计算不超过 $k$ 的边数使用树状数组维护一下即可。复杂度 $O(N^{\frac{5}{3}}\log_2N)$ 。

F

化简

$\sum_{x_1=1}^n\sum_{x_2=1}^n\sum_{y_1=1}^m\sum_{y_2=1}^m\frac {(x_1y_2+x_2y_1)\bmod (\max\{x_1,x_2\}\times \max\{y_1,y_2\})}{\gcd(\max\{x_1,x_2\},\max\{y_1,y_2\})}$

先把求和上下指标做一些处理

$\begin{aligned} &[1\leq x_1\leq n][1\leq x_2\leq n][1\leq y_1\leq m][1\leq y_2\leq m]\\ =&\big([x_1<x_2]+[x_2<x_1]+[x_1=x_2]\big)\big([y_1<y_2]+[y_2<y_1]+[y_1=y_2]\big)\\ =&[x_1<x_2][y_1<y_2]+[x_1<x_2][y_2<y_1]+[x_2<x_1][y_1<y_2]+[x_2<x_1][y_2<y_1]\\+&[x_1<x_2][y_1=y_2]+[x_2<x_1][y_1=y_2]+[x_1=x_2][y_1<y_2]+[x_1=x_2][y_2<y_1]\\+&[x_1=x_2][y_1=y_2]\\ =&2[x_1<x_2][y_1<y_2]+2[x_1>x_2][y_1<y_2]+2\big([x_1<x_2][y_1=y_2]+[x_1=x_2][y_1<y_2]\big)+[x_1=x_2][y_1=y_2] \end{aligned}$

将 $[ x_1 < x_2 ] [ y_1 < y_2 ]$ 拆一下

$\begin{aligned} &[1\leq x_1<x_2][1 \leq y_1<y_2]\\ =&\big([0\leq x_1<x_2]-[0=x_1<x_2]\big)\big([0\leq y_1<y_2]-[0=y_1<y_2]\big)\\ =&[0\leq x_1<x_2][0\leq y_1<y_2]-[0=x_1<x_2][0\leq y_1< y_2]\\-&[0\leq x_1\leq x_2][0= y_1<y_2]+[0=x_1<x_2][0=y_1<y_2]\\ \end{aligned}$

带回去得到结果

$\begin{aligned} &2[0\leq x_1<x_2][0\leq y_1<y_2]\\ -&2([0=x_1<x_2][0\leq y_1< y_2]+[0\leq x_1\leq x_2][0= y_1<y_2])\\ +&2[0=x_1<x_2][0=y_1<y_2]\\ +&2[x_1>x_2][y_1<y_2]\\ +&2\big([x_1<x_2][y_1=y_2]+[x_1=x_2][y_1<y_2]\big)\\ +&[x_1=x_2][y_1=y_2] \end{aligned}$

现在分别考虑每一项

$[0\leq x_1<x_2][0\leq y_1<y_2]$

引理 $(ax+by)\bmod (ab)(0\leq x<b,0\leq y<a)$ 将集合 $S=\{(x,y)\mid 0\leq x<b,0\leq y<a\}$ 映射到集合 $T=\{k\gcd(a,b)\mid 0\leq k<\frac {ab}{\gcd(a,b)}\}$ 上。其中 $T$ 中的每个数字有恰好 $\gcd(a,b)$ 个原象。
证明记 $d=\gcd(a,b)$ 。
首先显然能够看出， $\forall x,y,d|(ax+by)\bmod (ab)$ 。
则 $\forall x,y$ ，设 $(ax+by)\bmod(ab)=kd$ ，则有 $\big(a((x+x_0)\bmod b)+b((y+y_0)\bmod a)\big)\bmod (ab)=(k+1)d$ ，其中 $x_0,y_0$ 为满足 $ax_0+by_0=d$ 的任意整数解。
利用这种方法，对于任意满足 $(ax+by)\bmod(ab)=kd$ 的 $(x,y)$ ，都能分别构造出满足 $(ax'+by')\bmod(ab)=(k+1)d,(k+2)d,...,0,...,(k-1)d$ 的 $(x',y')$ 。
因此 $\forall k_1,k_2$ ， $\big|\{(x,y)\mid (ax+by)\bmod(ab)=k_1d\}\big|=\big|\{(x,y)\mid (ax+by)\bmod(ab)=k_2d\}\big|=\gcd(a,b)$ 。

利用这个引理，可以将 $\bmod$ 符号去掉。

$\begin{aligned} &\sum_{x_1=0}^n\sum_{x_2=x_1+1}^n\sum_{y_1=0}^m\sum_{y_2=y_1+1}^m\frac {(x_1y_2+x_2y_1)\bmod (x_2y_2)}{(x_2,y_2)}\\ =&\sum_{x_2=1}^n\sum_{y_2=1}^m\frac 1{(x_2,y_2)}\sum_{x_1=0}^{x_2-1}\sum_{y_1=0}^{y_2-1}(x_1y_2+x_2y_1)\bmod (x_2y_2)\\ =&\sum_{x_2=1}^n\sum_{y_2=1}^m \frac 1{(x_2,y_2)}\sum_{a=0}^{x_2y_2-1}[(x_2,y_2)|a]a(x_2,y_2)\\ =&\frac 12 \sum_{x_2=1}^n\sum_{y_2=1}^m (x_2,y_2)\bigg(\big(\frac {x_2y_2}{(x_2,y_2)}\big)^2-\frac {x_2y_2}{(x_2,y_2)}\bigg) \end{aligned}$

拿出来前面一项

$\begin{aligned} &\sum_{x_2=1}^n\sum_{y_2=1}^m \frac {x_2^2y_2^2}{(x_2,y_2)}\\ =&\sum_d \frac 1d \sum_{x_2=1}^n\sum_{y_2=1}^m x_2^2y_2^2[(x_2,y_2)=d]\\ =&\sum_d d^3 \sum_{x_2=1}^{\frac nd}\sum_{y_2=1}^{\frac md} x_2^2y_2^2[x_2\perp y_2]\\ =&\sum_d d^3 \sum_t t^4\mu(t)\sum_{x_2=1}^{\frac n{dt}}\sum_{y_2=1}^{\frac m{dt}} x_2^2y_2^2\\ =&\sum_T S_2\big(\lfloor \frac nT \rfloor \big)S_2\big(\lfloor \frac mT \rfloor \big)\sum_{d|T}d^4\mu(d)\big(\frac Td\big)^3\\ \end{aligned}$

得

$\begin{aligned} &[0\leq x_1<x_2][0\leq y_1<y_2]\\ =&\frac 12\sum_T S_2\big(\lfloor \frac nT \rfloor \big)S_2\big(\lfloor \frac mT \rfloor \big)\sum_{d|T}d^4\mu(d)\big(\frac Td\big)^3-\frac {nm(n+1)(m+1)}{8} \end{aligned}$

$[0=x_1<x_2][0\leq y_1<y_2]$

$\begin{aligned} &\sum_{x_2=1}^{n}\sum_{y_1=0}^{m}\sum_{y_2=y_1+1}^{m}\frac {(0+x_2y_1)\bmod (x_2y_2)}{(x_2,y_2)}\\ =&\sum_{x_2=1}^{n}\sum_{y_1=0}^{m}\sum_{y_2=y_1+1}^{m}\frac {x_2y_1}{(x_2,y_2)} \end{aligned}$

$[0=x_1<x_2][0=y_1<y_2]$

由于

$(0+0)\bmod (x_2y_2)\equiv 0$

所以结果为 $0$

$[x_1>x_2][y_1<y_2]$

$\begin{aligned} &\sum_{x_2=0}^n\sum_{x_1=x_2+1}^n\sum_{y_1=0}^m\sum_{y_2=y_1+1}^m\frac {(x_1y_2+x_2y_1)\bmod (x_1y_2)}{(x_1,y_2)}\\ =&\sum_{x_1=1}^n\sum_{y_2=1}^m\frac 1{(x_1,y_2)}\sum_{x_2=0}^{x_1-1}\sum_{y_1=0}^{y_2-1} x_2y_1 \\ =&\sum_{x_1=1}^n\sum_{y_2=1}^m\frac {x_1y_2(x_1-1)(y_2-1)}{4(x_1,y_2)}\\ =&\frac 14\sum_{d}\frac 1d\sum_{x_1=1}^n\sum_{y_2=1}^m x_1y_2(x_1-1)(y_2-1)[(x_1,y_2)=d]\\ =&\frac 14\sum_d\sum_{x_1=1}^{\frac nd}\sum_{y_2=1}^{\frac md}(x_1^2y_2^2d^3-x_1y_2^2d^2-x_1^2y_1d^2+x_1y_1d)[x_1\perp y_2]\\ =&\frac 14\sum_d\sum_t\mu(t)\sum_{x_1=1}^{\frac n{dt}}\sum_{y_2=1}^{\frac m{dt}}(x_1^2y_2^2d^3t^4-x_1y_2^2d^2t^3-x_1^2y_1d^2t^3+x_1y_1dt^2)\\ =&\frac 14\sum_T\bigg(S_2\big(\frac nT\big)S_2\big(\frac mT\big)\sum_{d|T}d^4\mu(d)\big(\frac {T}{d}\big)^3-\big(S_1\big(\frac nT\big)S_2\big(\frac mT\big)+S_2\big(\frac nT\big)S_1\big(\frac mT\big)\big)\sum_{d|T}d^3\mu(d)\big(\frac {T}{d}\big)^2+S_1\big(\frac nT\big)S_1\big(\frac mT\big)\sum_{d|T}d^2\mu(d)\big(\frac {T}{d}\big)\bigg) \end{aligned}$

$[x_1=x_2][y_1<y_2]$

$\begin{aligned} &\sum_{x_2=1}^{n}\sum_{y_1=1}^{m}\sum_{y_2=y_1+1}^{m}\frac {x_2(y_1+y_2)\bmod (x_2y_2)}{(x_2,y_2)}\\ =&\sum_{x_2=1}^{n}\sum_{y_1=1}^{m}\sum_{y_2=y_1+1}^{m}\frac {x_2y_1}{(x_2,y_2)} \end{aligned}$

和 $[0=x_1<x_2][y_1<y_2]$ 相同，因此对应项抵消。对于对称的两项同样抵消了。

$[x_1=x_2][y_1=y_2]$

$(x_2y_2+x_2y_2)\bmod (x_2y_2)\equiv 0$

结论

删掉抵消的以及和为0的项，所求的结果为

$\begin{aligned} &2[0\leq x_1<x_2][0\leq y_1<y_2]+2[x_1>x_2][y_1<y_2] \end{aligned}$

带入前面得到的结论，最终所求的和式就是

$\begin{aligned} &\sum_T S_2\big(\lfloor \frac nT \rfloor \big)S_2\big(\lfloor \frac mT \rfloor \big)\sum_{d|T}d^4\mu(d)\big(\frac Td\big)^3-\frac {nm(n+1)(m+1)}{2}\\ +&\frac 12\sum_T\bigg(S_2\big(\frac nT\big)S_2\big(\frac mT\big)\sum_{d|T}d^4\mu(d)\big(\frac {T}{d}\big)^3-\big(S_1\big(\frac nT\big)S_2\big(\frac mT\big)+S_2\big(\frac nT\big)S_1\big(\frac mT\big)\big)\sum_{d|T}d^3\mu(d)\big(\frac {T}{d}\big)^2+S_1\big(\frac nT\big)S_1\big(\frac mT\big)\sum_{d|T}d^2\mu(d)\big(\frac {T}{d}\big)\bigg) \end{aligned}$

记 $S_a(\frac nT)S_b(\frac mT)$ 为 $S_{ab}(T)$ ，记 $\sum_{d|T}d^a\mu(d)(\frac {T}{d})^b$ 为 $c_{ab}(T)$ ，则上式可以写作

$\frac 12\bigg(\sum_T 3S_{22}(T)c_{43}(T)-(S_{12}(T)+S_{21}(T))c_{32}(T)+S_{11}(T)c_{21}(T)\bigg)-\frac {nm(n+1)(m+1)}{4}$

筛

综上，要筛这三个函数的前缀和

$\begin{aligned} c_{43}(n)&=\sum_{d|n} d^4\mu(d)\big(\frac {n}{d}\big)^3=n^3\sum_{d|n}d\mu(d)\\ c_{32}(n)&=\sum_{d|n} d^3\mu(d)\big(\frac {n}{d}\big)^2=n^2\sum_{d|n}d\mu(d)\\ c_{21}(n)&=\sum_{d|n} d^2\mu(d)\big(\frac {n}{d}\big)=n\sum_{d|n}d\mu(d)\\ \end{aligned}$

都是类似的。以 $c_{43}$ 为例，

$\begin{aligned} &\sum_{i=1}^n c_{43}(n)\\ =&\sum_{i=1}^n i^3\sum_{d|i}d\mu(d)\\ =&\sum_{d}d^4\mu(d)S_3\big(\lfloor \frac nd \rfloor \big) \end{aligned}$

然后要求 $\alpha(n)=n^4\mu(n)$ 的前缀和，由