2021牛客暑期多校训练营7

排名	当场过题数	至今过题数	总题数
21/1294（校内3/19）	4	9	11

A

upsolved by TYB

题意

给一张\(n\)​个点的完全图，边有边权，若一个边集能将\(n\)个点连通，则为合法边集，求所有合法边集边权乘积与边集大小乘积之和。

\(n\le20\)，对\(998244353\)取模

题解

先考虑不要求乘上边数怎么做。令\(f_S\)表示边的端点都在\(S\)中时，使\(S\)连通的边集权值和，\(g_S\)表示边的端点都在\(S\)中的边集权值和。则\(G=\sum_{i>0}\frac{F^i}{i!}=\exp(F)-1\)，这里的乘法为不相交集合并，即\((f\times g)_S=\sum_{L\subseteq S}\sum_{R\subseteq S}[L\bigcup R=S][L\bigcap R=\emptyset]f_Lg_R\)​。\(G\)很好求，\(F=\ln(G+1)\)，只要做一个集合幂级数\(\ln\)即可求出\(F\)，复杂度\(O(n^22^n)\)。在本题中，运用生成函数的思想，不妨认为\(f_S\)和\(g_S\)​都是多项式\(\sum_ia_ix^i\)，\(a_i\)表示边集权值和，\(i\)表示边数，代入上式依旧成立。那么最后的答案为\(\sum_ia_i\times i=f'_{2^n-1}(1)\)。所以实际上我们只需要维护\((f(1),f'(1))\)这个二元组即可。

求集合幂级数\(\ln\)的方法有点抽象，在这里简述一下：第一步：对\(G+1\)按照每个状态\(S\)中\(1\)的个数求得到其占位多项式。第二步：对该占位多项式做\(FMT\)（即或卷积）。第三步：对集合幂级数的每个状态\(S\)（即一个形式幂级数）求出其\(\ln\)。第四步：对该占位多项式做\(IFMT\)。

第三步的具体方法如下：

\(F=\ln(G+1)\)

\(F'(G+1)=G'\)

\(F'_i=G'_i-\sum_{j=1}G_jF'_{i-j}\)

B

upsolved by TYB

题意

给出两个序列\(\{a_n\},\{b_n\}\)，其中\(b\)是\(01\)序列，\(q\)次操作，一是将\(a_x\)改成\(y\)；二是将\(b_{l\dots r}\)取反，即\(01\)​互换；三是询问\(l,r\)​，维护一个位置集合\(S\)，初始时\(S=\{l\}\)，设\(S\)中的最大值为\(i\)，每次找到一个使\(a_j\ge a_i\)的最小的\(j\)，若不存在这样的\(j\)或者\(j>r\)则结束流程，否则将\(j\)加入\(S\)并继续该流程，设\(S\)中第\(i\)小的数为\(p_i\)​，最后求\(\sum_{i=1}^{|S|-1}b_{p_i}\bigoplus b_{p_{i+1}}\)。

\(q,n\le2\times10^5\)

题解

原来觉得\(\log\)​数据结构不可做，原来是个经典的问题。先考虑只求\(|S|\)​怎么做。定义\(ans(x,mx)\)​为当前最大值为\(mx\)​，进入\(x\)​这个区间后能再选多少个数，比如\(mx=3\)​，在\([2,4,1,5]\)​这个区间能再选\(\{4,5\}\)​两个数，\(mx=1\)​则能再选三个数。线段树每个节点\(x\)​维护区间最大值\(mx[x]\)​、\(ans(x,-\inf)\)​、\(ans(rc,mx[lc])\)​​，设函数\(calc(x,v)\)​返回\(ans(x,v)\)​，那么每个询问都可以拆成若干个\(calc(x,v)\)​，分两种情况：若\(v\le mx[lc]\)，则无论如何在离开\([l,mid]\)这段区间时，最大值一定为\(mx[lc]\)，所以这种情况的答案为\(calc(lc,v)+ans(rc,mx[lc])\)；否则，相当于直接跳到\([mid+1,r]\)这段区间，答案为\(calc(rc,v)\)。可以发现，无论哪种情况，都只会递归到其中一边，所以\(calc\)的复杂度是\(O(\log n)\)的；单点修改时，每次update也需要用到\(calc\)，共\(\log n\)次，复杂度\(O(\log^2n)\)；询问时拆成\(\log n\)个\(calc\)，复杂度也是\(O(\log^2n)\)。对于本题，只要将维护的信息略作修改即可，重要的是这一种套路。

C

upsolved by Suspicious String

题意

\(q\) 组询问，每组询问给出 \(a,b\)，每次可以令 \(a\leftarrow a+\text{popcount}(a)\)，求不小于 \(b\) 的能得到的最小的 \(a\)，输出 \(\sum_{i=1}^q ia_i\bmod 2^{64}\)。

\(1\leq q\leq 10^7\)，\(1\leq a\leq b<2^{64}\)

题解

面对垃圾卡常题失去语言能力，可参考官方题解脑补，脑壳特疼，待填。

UPD: 填了。

首先注意到单次步长不超过 \(64\)，因此对于满足 \(64x\geq a\) 的任意 \(x\)，都存在 \(y<64\)，使得 \(a\) 经过 \(64x+y\)。对于一个 \(a\)，均能拆为 \(64x+y\) 的形式，方便起见，我们称 \(x\) 为高位值，称 \(y\) 为低位值。显然地，二进制下高位值共 \(58\) 位，低位值共 \(6\) 位。

考虑 \(x\) 的各个二进制位，若能从某个 \(a\) 快速地转移到某位进位的位置，就可以处理较为方便地回答询问。

可以预处理 \(u_{i,j,k}\) 表示高位值 \(x\) 末尾共有 \(i\) 位是 \(0\)，高位值除去末尾 \(i\) 位的 \(\text{popcount}\) 为 \(j\)，低位值为 \(y\) 时，依次步进到 \(x\) 的末尾第 \(i+1\) 位发生进位时的低位值。也即：\(a\) 此时为 \(64x+y\)，二进制为 \(\underbrace{\mathtt{xx...xx}}_{\text{popcount}=j}\underbrace{\mathtt{00...00}}_{i\;\text{digits}}\underbrace{\mathtt{yyyyyy}}_{\text{value}=k}\)，\(u_{i,j,k}\) 即为步进过程中 \(\mathtt{xx...xx}\) 段增加 \(1\) 时最小的低位值，并且容易发现此时 \(\mathtt{00...00}\) 段仍为 \(\mathtt{00...00}\)。特殊地，当 \(i=0\) 时表示不存在 \(\mathtt{00...00}\) 段。

利用 \(u_{i,j,k}\) 的信息，可以从低位到高位依次将 \(a\) 的高位值快速进位到与 \(b\) 的高位值在二进制下具有相同前缀，并且除去前缀后 \(a\) 的高位值剩余位均为 \(0\)，再从高位到低位依次将 \(a\) 的高位值的前缀补齐到与 \(b\) 的高位值相同。高位值相同时仅需考虑 \(a\) 与 \(b\) 的低位值，暴力即可。回答单次询问的复杂度为 \(O(64)\)，并不能通过本题。

采用分块的思想，将高位值中连续 \(B\) 位作为一个块预处理，代码实现中选取了 \(B=7\)，因此真实值 \(a\) 二进制下被划分为了以下形式：

\[\mathtt{...}\underbrace{\mathtt{ccccccc}}_{\text{block}\;2}\underbrace{\mathtt{bbbbbbb}}_{\text{block}\;1}\underbrace{\mathtt{aaaaaaa}}_{\text{block}\;0}\mathtt{yyyyyy}\]

我们约定块的编号由低位向高位以 \(0\) 起始依次编号，因此共有 \(\left\lceil {58\over B}\right\rceil\) 个块。块内低位向高位以 \(1\) 起始依次编号。

类似 \(u_{i,j,k}\)，我们定义以下辅助 \(a\) 快速步进的预处理值：

• \(f_{i,j,k}\) 表示 \(a\) 的高位值 \(x\) 的 \(\text{popcount}\) 为 \(i\)，低位值为 \(j\) 时，步进到高位值不变但低位值不小于 \(k\) 时的最小步进增量。
• \(g_{i,j,k,l,m}\) 表示 \(a\) 的高位值 \(x\) 在第 \(0\) 块至第 \(i-1\) 块均为 \(0\)，高位值在第 \(i\) 块内末尾 \(l\) 位值为 \(m\)，高位值的第 \(i\) 块内除去末尾 \(l\) 位的剩余 \(B-l\) 位与第 \(i+1\) 块至第 \(\left\lceil {58\over B}\right\rceil\) 块的 \(\text{popcount}\) 之和为 \(j\)，低位值为 \(k\) 时，步进到高位值第 \(i\) 块内末尾第 \(l+1\) 位发生进位时的最小的低位值。
• \(h_{i,j,k,l,m}\) 表示 \(a\) 的高位值 \(x\) 在第 \(0\) 块至第 \(i-1\) 块以及第 \(i\) 块内末尾 \(l\) 位均为 \(0\)，高位值的第 \(i\) 块内除去末尾 \(l\) 位的剩余 \(B-l\) 位与第 \(i+1\) 块至第 \(\left\lceil {58\over B}\right\rceil\) 块的 \(\text{popcount}\) 之和为 \(j\)，低位值为 \(k\) 时，步进到高位值其余位不变但第 \(i\) 块内末尾 \(l\) 位值为 \(m\) 时的最小的低位值。

由 \(g,h\) 的定义可以得到 \(0\leq l<B\)，\(0\leq m<2^l\)。

具象地，对 \(g,h\) 作出如下说明便于理解：

\[g_{i,j,k,l,m}:\rlap{\underbrace{\phantom{\mathtt{...x..x}}}_{\text{popcount}=j}}\mathtt{...}\;\overbrace{\mathtt{x..x}\;\underbrace{\mathtt{m..m}}_{\begin{matrix}l\;\text{digits}\\\text{value}=m\end{matrix}}}^{\text{block}\;i}\;\mathtt{00..00}\;\underbrace{\mathtt{yyyyyy}}_{\text{value}=k} \longrightarrow \mathtt{...}\;\overbrace{\mathtt{X..X}\;\underbrace{\mathtt{0..0}}_{l\;\text{digits}}}^{\text{block}\;i}\;\mathtt{00..00}\;\underbrace{\mathtt{YYYYYY}}_{\text{value}=g_{i,j,k,l,m}}\]

其中 \((\mathtt{...X..X})_2=(\mathtt{...x..x})_2+1\)，\(\mathtt{YYYYYY}\) 即为 \(g_{i,j,k,l,m}\)，即满足条件的最小的低位值。

\[h_{i,j,k,l,m}:\rlap{\underbrace{\phantom{\mathtt{...x..x}}}_{\text{popcount}=j}}\mathtt{...}\;\overbrace{\mathtt{x..x}\;\underbrace{\mathtt{0..0}}_{l\;\text{digits}}}^{\text{block}\;i}\;\mathtt{00..00}\;\underbrace{\mathtt{yyyyyy}}_{\text{value}=k} \longrightarrow \mathtt{...}\;\overbrace{\mathtt{x..x}\;\underbrace{\mathtt{m..m}}_{\begin{matrix}l\;\text{digits}\\\text{value}=m\end{matrix}}}^{\text{block}\;i}\;\mathtt{00..00}\;\underbrace{\mathtt{YYYYYY}}_{\text{value}=h_{i,j,k,l,m}}\]

其中 \(\mathtt{YYYYYY}\) 即为 \(h_{i,j,k,l,m}\)，即满足条件的最小的低位值。

根据定义容易得到 \(f_{i,j,k}\) 的递推关系：

\[f_{i,j,k}=\begin{cases}0&,j\geq k\\i+\text{popcount}(j)&,j+i+\text{popcount}(j)\geq k\\f_{i,j+i+\text{popcount}(j),k}+i+\text{popcount}(j)&,j+i+\text{popcount}(j)<k\end{cases}\]

计算 \(g_{i,j,k,l,m}\) 时需要使用 \(f_{i,j,k}\) 的值：

\[g_{i,j,k,l,m}=\begin{cases}(k+f_{j,k,64})\bmod 64&,l=0\wedge i=0\\g_{i-1,j+1,g_{i-1,j,k,B-1,0},B-1,0}&,l=0\wedge i\neq 0\\g_{i,j+1,k,l-1,m\,\bmod\,2^{l-1}}&,l>0\wedge m\geq 2^{l-1}\\g_{i,j+1,g_{i,j,k,l-1,m\,\bmod\,2^{l-1}},l-1,0}&,l>0\wedge m<2^{l-1}\end{cases}\]

而计算 \(h_{i,j,k,l,m}\) 时需要使用 \(g_{i,j,k,l,m}\) 的值：

\[h_{i,j,k,l,m}=\begin{cases}k&,l=0\\h_{i,j+1,g_{i,j,k,l-1,0},l-1,m\,\bmod\,2^{l-1}}&,l>0\wedge m\geq 2^{l-1}\\h_{i,j,k,l-1,m\,\bmod\,2^{l-1}}&,l>0\wedge m<2^{l-1}\end{cases}\]

分类讨论即可得到上述关系式。预处理时需要注意 \(g,h\) 不同的递推顺序。

容易发现，状态数总共为 \(\left\lceil{58\over B}\right\rceil\cdot 58\cdot64\cdot B\cdot 2^{B-1}\)，因此预处理的总时间复杂度为 \(O(58^2\cdot64\cdot 2^{B-1})\)。

回答一个询问时，将 \(a\) 的高位值与低位值分离处理。

先从低位向高位依次处理每个块，并维护低位值。设当前为第 \(i\) 块，块内当前 \(a\) 所有二进制位的值为 \(m\)，有以下两种情况：

• 若除当前块外不存在更高的位使得当前 \(a\) 的高位值与 \(b\) 的高位值存在差异，则找到块内最高的差异位，设其为块内末尾第 \(l\) 位。由 \(a<b\) 可保证这一位上 \(a\) 为 \(0\) 且 \(b\) 为 \(1\)，因此只需要将 \(a\) 快速步进到 \(g_{i,*,k,l-1,m\,\bmod\,2^{l-1}}\) 对应位置即可将 \(a\) 的差异位变为 \(1\)，并且高位值中低于差异位的所有位均为 \(0\)，此时 \(a\) 的高位值与 \(b\) 的高位值具有相同的前缀。\(*\) 处的 \(\text{popcount}\) 具体值根据定义即可计算。
• 若不然，则存在仍未访问的块，块中当前 \(a\) 的高位值与 \(b\) 的高位值存在差异。因此为了后续的快速步进，需要将当前块均步进为 \(0\)。具体地，若 \(m\geq 2^{B-1}\) 则将 \(a\) 快速步进到 \(g_{i,*,k,B-1,m\,\bmod\,2^{B-1}}\)，若 \(m<2^{B-1}\) 则将 \(a\) 快速步进到 \(g_{i,*+1,g_{i,*,k,B-1,m},B-1,0}\)，维护 \(a\) 的高位值与低位值即可。

此时 \(a\) 的高位值与 \(b\) 的高位值已有相同的前缀，并且除去前缀后 \(a\) 的高位值剩余位均为 \(0\)，这为后续的补齐步进提供了便利。

对于差异位所在的块，设其为第 \(i\) 块，块内 \(b\) 所有二进制位的值为 \(m\)，若 \(a\) 的高位值与 \(b\) 的高位值仍有差异，则该块仍需补齐。设差异位为块内末尾第 \(l\) 位，只需将 \(a\) 快速步进到 \(h_{i,*,k,l-1,m\,\bmod\,2^{l-1}}\) 即可。

再自差异位所在块起，由高位向低位依次处理剩余每个块。设当前为第 \(i\) 块，块内 \(b\) 所有二进制位的值为 \(m\)。此时块内只需将当前 \(a\) 补齐至 \(b\) 即可。具体地，若 \(m\geq 2^{B-1}\) 则将 \(a\) 快速步进到 \(h_{i,*+1,g_{i,*,k,B-1,0},B-1,m\,\bmod\,2^{B-1}}\)，若 \(m<2^{B-1}\) 则将 \(a\) 快速步进到 \(h_{i,*,k,B-1,m}\)，维护 \(a\) 的高位值与低位值即可。

现在 \(a\) 和 \(b\) 的高位值 \(x\) 均相同，只需考虑低位值。设当前 \(a\) 低位值为 \(y\)，\(b\) 低位值为 \(y'\)，简单地令 \(a\leftarrow a+f_{\text{popcount}(x),y,y'}\) 即可得到最终答案。

单次询问时间复杂度 \(O(\left\lceil{58\over B}\right\rceil)\)。

降低常数小技巧：

• \(g,h\) 使用 char 类型存储。
• 将数组中较小维向前调整可以加速访问高维数组。

或许可以定义 \(l=B\) 时的 \(g,h\) 方便运算？反正 AC 了，不管了。

D

upsolved by

题意

题解

E

upsolved by TYB

题意

取石子游戏，\(n\)堆石子\(m\)个数，每次能从一堆取石子，每次取的石子数\(x\)满足\(\mu(x)=1\)或\(x\)为给定的\(m\)个数之一，给出每堆石子的取值范围\([l_i,r_i]\)，求所有\(\Pi_{i=1}^n(r_i-l_i+1)\)种情况中，先手获胜的有多少种。

\(n\le10^6,m\le5,l_i\le r_i\le10^5\)

题解

本题的求解分为两部分，一是求\(sg\)函数，二是求方案数。

对于第一部分，注意到\(m\)​很小，可以将\(m=0\)时的表打出来，由于\(\mu(x)=1\)的数并不算太多，这个\(sg\)值会比较小，这种情况下好像是不超过\(70\)的。据出题人模拟退火一天跑出来的结果，\(sg\)值不超过\(230\)。这样我们可以开\(230\)个bitset，第\(i\)个bitset的第\(j\)​​个位置表示\(j\)能到达的状态中是否有\(sg\)值为\(i\)的，用来加速求\(sg\)​值的过程。设值域为\(V\)，本部分复杂度为\(\mathcal{O}(\frac{V^2}{w}+230V)\)。

对于第二部分，显然可以暴力FWT，显然跑不过去，考虑如何优化。在FWT的过程中，每个位置对FWT后得到的数组贡献是固定的，且不同位置的贡献可以直接相加，所以可以用一个前缀和\(sum_{i,j}\)表示前\(i\)个\(sg\)值对\(j\)​这个位置的贡献，然后对于每堆石子我们就可以\(\mathcal{O}(256)\)得其FWT后的数组。那么这个贡献怎么算呢？考虑异或FWT是如何构造变换的，摘录oi-wiki部分资料如下：

异或的卷积是基于如下原理：

若我们令\(i\&j\)中\(1\)数量的奇偶性为\(i\)与\(j\)的奇偶性，那么\(i\)与\(k\)的奇偶性异或\(j\)与\(k\)的奇偶性等于\(i\ xor\ j\)与\(k\)的奇偶性。

对于\(FWT[A]\)的运算其实也很好得到。

公式如下：\(A_i=\sum_{C_1}A_j-\sum_{C_2}A_j\)

(\(C_1\)表示\(i\&j\)奇偶性为\(0\)，\(C_2\)表示\(i\&j\)的奇偶性为\(1\))

利用该公式即可计算每个位置的贡献，这一部分的复杂度为\(\mathcal{O}(256V+256n)\)。

F

solved by JLK

题意

给定两棵以1为根的树。找到最大的点集，使得在第一棵树上，点集联通，并且对于任意两个点，一个是另一个的祖先。而同时在第二棵树上，任意两个点不是祖先关系。输出最大点集大小。

\(1 \le n \le 3\times 10^5\)

题解

实际上就是在第一棵树的从根开始的一条链上选一个连续区间的点。考虑怎样会冲突，就是两个点在第二棵树的子树有交集，也就是在第二棵树上子树dfs序有交集。

利用主席树，可以在dfs第一棵树的同时找到和每个点最近的一个冲突祖先。就是以第二棵树的dfs序为下标，第一棵树上的深度为权值，每次区间取max和区间求max。得到这个之后，符合条件的区间一定是，区间里所有点的深度最大冲突点小于区间的最小深度。这可以用倍增来处理。

\(O(nlogn)\)

G

upsolved by

题意

题解

H

solved by TYB

题意

签到。

题解

略。

I

solved by YZW

题意

签到。

题解

略。

J

upsolved by JLK

题意

给定有向图，问如下形式的假Floyd算法可以跑出多少正确的点对距离。

for i from 1 to n
  for j from 1 to n
    for k from 1 to n
      dis[i][j] <- min(dis[i][j], dis[i][k] + dis[k][j])

\(n \le 2000, m \le 5000,0 \lt w \le 10^4\)

题解

首先肯定要用\(n\)次Dij求出所有点对的正确距离。

考虑过程中怎样才会转移到一个对的距离。

如果某条边就是最短路，那么肯定是对的。

否则，对于\((i,j)\)​，要找到一个\(k\)​，使得\(i\to k,k\to j\)​的距离都是对的，并且\(k\)​有可能在\(i\to j\)​的最短路上。

前者可以维护两个bitset，表示从某个点开始或结束，有哪些点的距离是对的。后者就要考虑相对关系。可以在枚举\(i\)​的时候，按照从\(i\)​​开始的正确距离排序，然后从小到大枚举，假设当前点为\(x\)​。如果\(x\)​加上\((x,y)\)​的边可以转移到\(y\)​的正确距离，那么就说明\(i\to x\)​最短路上经过的点也有可能会在\(i\to y\)上，同样用bitset维护，每次或一下即可。

处理出后者的bitset，在按照假算法的顺序枚举\((i,j)\)，依次判断，不断维护前者的bitset即可。

\(O(nm\log n+\frac{n^2m}{64})\)

实际上还有一种复杂度更优秀并且可以处理\(w=0\)的方法，但是太抽象了没看懂。留坑待填。

K

solved by TYB

题意

给一个序列\(\{a_n\}\)，\(q\)次询问，每次给出\(l,r,k\)，求\(a_{l\dots r}\)的数在模\(k\)意义下，每次可以选择一个连续区间\(+1\)或\(-1\)，将全部数变为\(0\)的最小次数。

\(n\le2\times 10^5,q\le10^5,k\le2^{30},a_i\in[0,k)\)

题解

考虑单次询问怎么做。首先将区间里的数差分（\(a_l\)不变），那么区间操作可以转化为对两个或一个任意位置的操作，在模\(k\)意义下转正后排序，最优策略一定是选择前面连续的一段都减到\(0\)，后面连续的一段都加到\(k\)，枚举分界点，设有\(x\)个数加到\(k\)，则答案为前面一段的和与\(xk\)减后面一段的和的最大值，设差分后转正的数之和为\(S\)，则也可以写成\(\max(xk-\)前\(x\)大数之和\(,S-\)前\(x\)大数之和\()\)。注意到前者随\(x\)的增大单调增大，后者单调减小，则这个东西的最小值在两者最接近的时候取到，即\(x\)的最优取值只可能是\(\lfloor\frac{S}{k}\rfloor\)和\(\lfloor\frac{S}{k}\rfloor+1\)，那么现在解决的就是一个区间前\(x\)大数之和的问题，由于负数还需要加上\(k\)，所以需要二分第\(x\)大数的值，再用主席树判断。复杂度\(O(n\log k+q\log^2k)\)。

记录

开局签HI。然后看其他题，都没有太可做的。（F题意读错了）

后来纠正了F题意，JLK冲了一发\(O(nlog^2n)\)​的写法，T了(1:31)。

又换了\(O(nlogn)\)​写法，WA1后AC(2:17)。期间TYB和YZW讨论K。

TYB写K，WA1后AC(3:47)。

B想到一个\(O(n\sqrt n log n)\)​做法，怕T没敢写。选择冲J，最后有一个树套树写法，没时间了，也怕T。

总结

JLK：题目有点怪，也没什么办法。

Dirt

F(-2)

K(-1)