专题题解 - ARC 129
ARC 129
不太好评价难度的一场，因为这场的题基本上都是想到一个大概思路或者和题解类似的想法是很容易的，但在细节上整理出来，或是把公式推出来并不容易。
A. Smaller Xor
难度：$\bigstar$
题目大意：
给定 $n,l,r$，求整数 $m\in [l,r]$ 的数量，使得 $m\oplus n<n$，其中 $\oplus$ 为异或。
$1\leq n,l,r\leq 10^{18}$
题目解法：
显然 $m\oplus n<n$ 等价于 $m\ne 0$ 且 $m$ 的最高位在 $n$ 中对应为 $1$，所以我们将所有整数按照最高位分成形如 $[2^i,2^{i+1}-1]$ 这样的区间，将其中可行的区间与 $[l,r]$ 取交即可。
时间复杂度为 $O(\log n)$。
B. Range Point Distance
难度：$\bigstar$
题目大意：
给定 $n$ 个区间 $[l_1,r_1],\ldots,[l_n,r_n]$，对于每个 $i\in [1,n]$ 求出 $f(x)=\max\limits_{j\leq i}(dis(x,[l_j,r_j]))$ 的最小值，其中 $dis(x,[l,r])$ 表示 $x$ 到区间 $[l,r]$ 的距离。
$1\leq n\leq 2\times 10^5$
题目解法：
显然答案是 $\max\limits_{j\leq i} l_i-\min\limits_{j\leq i}r_j$ 与 $0$ 取 $\max$ 后的一半，上取整。
时间复杂度为 $O(n)$。
C. Multiple of 7
难度：$\bigstar$
题目大意：
给定 $n$，构造一个长度不超过 $10^6$ 的数字串 $S$，令 $w(l,r)$ 表示将 $S_l,\ldots,S_r$ 构成的非空子串看成十进制数对应的数值，你需要保证使得 $7\mid w(l,r)$ 的二元组 $(l,r)$ 的数量恰好为 $n$。
$1\leq n\leq 10^6$
题目解法：
考虑形如 $77\ldots77x77\ldots77y77\ldots77z\ldots$ 这样的数，并且假定所有 $7\mid w(l,r)$ 的 $l,r$ 都在同一段连续 $7$ 中，那么设每一段 $7$ 的长度为 $c_1,\ldots,c_m$，就有 $n=\sum\binom {c_i} 2$。
将 $n$ 分解成若干 $\binom x 2$ 的和，每次贪心选可能的最大的 $x$，那么大致估计一下最多分成不超过 $7$ 个 $\binom x 2$，我们现在要做的就是构造那些夹在两段 $7$ 之间的数，使得它们不会带来新的 $7\mid w(l,r)$，而由于总共只需要填 $6$ 个这样的数（因为共不超过 $7$ 段 $7$），利用抽屉原理，每次维护之前所有 $\bmod 7$ 的可能性，然后挑一个填进去不会得到 $\bmod 7=0$ 的情况的数即可。
和题解做法不太一样（还更复杂一些），时间复杂度 $O(\sqrt n)$。
D. -1+2-1
难度：$\bigstar\bigstar$
题目大意：
给定一个长度为 $n$ 的序列 $a_1,\ldots,a_n$，将它首位拼接，每次操作可以选择一个数将它 $+2$，然后将两边的数 $-1$，求最少要多少次操作能将所有数变为 $0$，或报告无解。
$3\leq n\leq 2\times 10^5$
题目解法：
其实还挺难的一题，接近三颗星难度。
考虑设第 $i$ 个位置操作了 $b_i$ 次，那么 $b_{i-1}+b_{i+1}-2b_i=a_i$，再对 $b_i$ 求差分 $c_i=b_i-b_{i-1}$，那么 $c_{i+1}-c_i=a_i$。
上面的定义中，$1$ 的前驱都是 $n$，$n$ 的后继都是 $1$，所以求一圈和之后有 $\sum a_i=0$，且 $\sum c_i=0$，根据 $\sum c_i=0$ 和 $c_{i+1}-c_i=a_i$ 可以解出所有 $c_i$（具体地，先求出 $c_i-c_1$，然后全加起来利用 $\sum c_i=0$ 得到 $c_1$，如果不是整数或者 $\sum a_i\ne 0$ 则无解）。
得到 $c_i$ 后我们可以求前缀和后进一步知道所有 $b_i-b_1$，那么令最小的 $b_i=0$，这样求出的 $\sum b_i$ 就是最小的操作次数了。
时间复杂度为 $O(n)$。
E. Yet Another Minimization
难度：$\bigstar\bigstar\bigstar$
题目大意：
有 $n$ 个变量 $x_1,\ldots,x_n$，每个 $x_i$ 都有 $m$ 种取值 $a_{i,1},\ldots,a_{i,m}$，必须从中选择一个，而选择 $a_{i,j}$ 需要代价 $c_{i,j}$，此外选定 $x_i$ 后还要付出额外代价 $\sum\limits_{i\ne j}|x_i-x_j|\times w_{i,j}$，求代价和的最小值。
$2\leq n\leq 50, 2\leq m\leq 5$
题目解法：
不难看出这是一道网络流题。
其实这题就是经典的切糕模型的拓展，不过如果不熟悉套路的话可能会被骗。
也就是说，将 $a_{i,1},\ldots,a_{i,m}$ 看作串联的一列边，割掉一条边表示选择这个 $a_{i,j}$，所以边的容量为 $c_{i,j}$。
再考虑如何把绝对值塞进去，在网络流模型中我们一般利用 $|x-y|=\sum\limits_{a} [x\leq a][y>a]+[y\leq a][x>a]$，思考一下在图上如何表达 $[x_i\leq a][x_j>a]$ 这件事，其实就是如果 $x_i$ 割在某段前缀，$x_j$ 割在某段后缀，那么就要加一个代价，所以直接连一条边在这个前缀右端点和后缀左端点之间即可，所以每一种 $a$ 都对应两排点中某两个点之间的一条边。
关于具体连边的实现，上述方案一种等价的表达是：对于一组 $p,q$，记 $A=\max(a_{i,p},b_{j,q}), B=\min(a_{i,p+1},b_{j,p+1})$，如果 $A<B$ 则在 $(i,p)$ 和 $(j,q)$ 确定的两个点之间连 $B-A$ 容量的双向边。
时间复杂度为 $O(\operatorname{MaxFlow}(nm,n^2m))$。
F. Let’s Play Tag
难度：$\bigstar\bigstar\bigstar$
题目大意：
在数轴上，你的初始位置为 $0$，有 $n$ 个在你左边的小朋友，第 $i$ 个到你的距离为 $l_i$，有 $m$ 个在你右边的小朋友，第 $i$ 个到你的距离为 $r_i$，其中 $l_i,r_i$ 都递增。
你随机生成一个包含 $n$ 个 $\text{L}$ 和 $m$ 个 $\text{R}$ 的字符串，然后依次看每个字符，如果是 $\text{L}$ 则向左走，否则向右走，碰到一个小朋友就会抓住他并且考虑下一个字符，直到所有小朋友都被抓住为止。
你的速度是 $2$，所有小朋友都会以 $1$ 的速度远离你，求所有可能生成的字符串对应的抓住所有小朋友的时间之和，答案对 $998244353$ 取模。
$3\leq n,m\leq 2.5\times 10^5$
题目解法：
自己做的时候大概推了下式子，但是没推完，只是发现最后是个 NTT 的形式，而题解也是类似的，所以感觉多推一下应该可以推出来。
对第一个和最后一个字符分类讨论，这里以第一个字符为 $\text{L}$，最后一个字符为 $\text{R}$ 为例。
首先要分析一些基本性质，那就是遇到一个形如 $\text{LR}$ 或者 $\text{RL}$ 的转角会让前面所有距离对当前答案的贡献 $\times 3$（这个可以手推一下），最后将每一步所产生的贡献加起来就是答案，所以如果走过一段距离之后还转了 $k$ 次，那么其贡献就是 $1+3+\ldots+3^k$。
以左边为例，假设在左边转角 $k$ 次，分别是在第 $a_1,\ldots,a_k=n$ 处，那么 $l_{a_i}-l_{a_{i-1}}$ 的贡献就是 $1+3+\ldots+3^{2(k-i)+1}$，进一步得到 $l_{a_i}$ 的贡献就是 $4\times 9^{k-i}$。
考虑一下现在的问题是怎么样的：我们需要在左边选取 $a_1,\ldots,a_k$，右边同样选取 $b_1,\ldots,b_k$，但由于 $a_k=n, b_k=m$ 所以实际上分别是从 $n-1$ 个里选 $k-1$ 个和从 $m-1$ 个里选 $k-1$ 个，而这时左边倒数第 $i$ 个元素的贡献就是其 $l$ 值乘上 $4\times 9^i$。
看到了这种形如 $\binom {n-1}{k-1}\binom {m-1}{k-1}$ 的东西，首先想到的是第二形式范德蒙德卷积，我们将右边选 $k-1$ 个改为右边不选 $m-k$ 个，那么利用范德蒙德卷积的解释知道这就相当于总共选 $k-1+m-k=m-1$ 个。
现在我们把选出的 $m-1$ 个元素中左边的放在前面，对于左边第 $i$ 个元素，如果它在被选的元素当中排名为 $j$，贡献为 $4\times 9^j$，再乘上方案数，对 $j$ 求和，也就是：
这明显是可以 NTT 的形式，直接卷积即可。
另外还有七个类似的卷积要算，所以总共是八次多项式乘法。
注意上面没有算特殊的左边第 $n$ 个和右边第 $m$ 个，但它们的贡献可以 $O(1)$ 计算。
时间复杂度为 $O((n+m)\log (n+m))$。