• 搬题人
  • 旋转序列：p_b_p_b
  • 交换豆子：Crysfly
  • 序列计数：Lynkcat
• 组题人
  • Lynkcat
• 题解：Crysfly

旋转序列

来源：

• Izborne Pripreme 2022 (Croatian IOI/CEOI Team Selection) Day 1, Problem B
• https://qoj.ac/contest/956/problem/4326

两个串之间 $1$ 匹配的次数总和为 $k\times l$，并且共有 $n$ 次匹配。

于是答案的上界为 $k\times l$ 个球放进 $n$ 个盒子，最小化最大的盒子中的 $1$ 个数，也就是 $\lceil \dfrac{k\times l}{n} \rceil$。

设 $ans = \lceil \dfrac{k\times l}{n} \rceil$，我们可以构造来达到这个上界：

• 对于第一个串，将前 $k$ 个位置变成 $1$。
• 对于第二个串，设这个串的前缀和数组为 $sum_i$。设 $sum_i = \min(\lfloor\dfrac{(i+1)\times ans}{k} \rfloor,l)$，然后差分即可。

交换豆子

来源：

• Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection) Day 2, Problem B
• https://qoj.ac/contest/1686/problem/8731

假设 C 是 1，P 是 0。

枚举第一行最后有多少个 $1$，由于 $1$ 的总个数不变，因此第一/第二行的 $1$ 的个数是确定的。

假设 $y$ 坐标为 $[1,2]$，$x$ 坐标为 $[1,n]$，此时我们想要最小化 移动步数 + 最后所有 $1$ 的 $x$ 坐标之和，答案就是这个值减去 $c_1(c_1+1)/2+c_2(c_2+1)/2$。

上下的移动步数是确定的，只需要最小化向右的移动步数（这些移动步数会增加 $x$ 坐标，每移动一步会有 $2$ 的代价，因为要增大 $x$ 坐标且多移动一次）。

接下来观察一些性质：

• 把一个 $1$ 从上往下调一定不优。
• 我们可以考虑先做若干次向右移动，直到某个时刻上下调整可以使得上下的个数满足要求，然后再上下调整。

什么情况下可以满足要求？若一列有 $2$ 个 $1$，则这列必须在第二行有一个 $1$，也就是有 $2$ 个 $1$ 的列不能超过 $c_2$ 个。

对于一个前缀的若干列，设有 $sum_i$ 个 $1$ 和 $i$ 列，则有 $\max(0,sum_i-i-c_2)$ 个 $1$ 必须向右调，需要花费的代价就是 $\sum 2\times \max(0,sum_i-i-c_2)$。

对于每种 $(c_1,c_2)$ 维护一个 $ans_{c_2}$，交换同一列两个时 $sum_i$ 不改变；交换不同列时只有 $1$ 个 $sum_i$ 会改变至多 $1$，只需要在 $ans$ 上区间加。

用线段树维护 $ans$ 数组，时间复杂度 $O(n+q\log n)$。

序列计数

来源：

• World Tour Finals 2022 Day1, Problem E
• https://atcoder.jp/contests/wtf22-day1/tasks/wtf22_day1_e

考虑转化成一个格路计数问题：

• 有一个 $n\times m$ 的网格，每次可以往上或往右走，要从 $(0,0)$ 走到 $(n,m)$。
• 每次从 $(i,j)\to (i+1,j)$ 就确定了 $a_{i+1}=j$，称 $(i,j)\to (i+1,j)$ 为横线。
• 对于求 $\{a_i-i\}$，可以转化成：画出 $y=x+k(-(n-1)\le k \le m)$ 的所有斜线，对于每条斜线，若有 $c$ 个横线在它的上方经过，则将 $ans_{n-c+1}\dots ans_n$ 加上 $1$。

考虑对于每条斜线算贡献，我们想要对于每个 $c$ 算出，有多少个方案恰有 $c$ 个横线在它的上方经过。

先特判掉所有没有触碰这条斜线的情况，这部分贡献可以 $O(n)$ 算出。

枚举这条斜线上的两个位置，钦定这是走的路径第一次、最后一次触碰斜线的位置。

我们有结论：

• 在一个 $n\times n$ 的网格中从 $(0,0)$ 走到 $(n,n)$，设所有 $(i,j)\to (i+1,j)$ 在对角线上方经过的次数为 $c$ 的方案数是 $ans_c$，则所有 $ans_c$ 相等，均为 $\frac{\binom{2n}{n}}{n+1}$。

于是钦定第一次、最后一次的触碰位置后，可贡献的 $c$ 是一个区间，且对于区间中的每个 $c$ 贡献相等。于是只需要在差分数组上修改。

直接枚举算贡献的复杂度是 $O(n^3)$ 的，考虑如何优化。

把 $y=x+k$ 的直线分成 $k\in [0,m-n]$ 和 $k\in [-(n-1),-1]$ 两部分。$[m-n+1,m]$ 和 $[-(n-1),-1]$ 是对称的。

考虑 $k\in [m-n+1,m]$ 的部分。

假设我们确定了触碰始终点之间的长度 $len$，则在差分数组上的修改位置是确定的。

枚举 $len$，那这段触碰始终点之间的方案是固定的 $\frac{\binom{2len}{len}}{len+1}$，前后两段的形式都是 $(0,0)\to (a,b)$ 且不触碰 $y=x+(b+1-a)$ 的折线个数（假设把后面一段对称一下）。

把这两段折线拼起来，就变成了一段折线，形式也是 $(0,0)\to (a,b)$ 不触碰 $y=x+(b+1-a)$，且 $a,b$ 只和 $len$ 有关。这样前后的方案数就变成了两个组合数相减的形式。

再枚举所有的 $k$ 加起来，发现加减的项抵消了，可以 $O(1)$ 计算同一个 $len$ 的方案数。于是这部分能做到 $O(n)$。

考虑 $k\in [0,m-n]$ 的部分。

由于我们是在差分数组上修改，我们可以只关心：对于所有触碰起点/终点，其方案数之和。起点和终点是相似的，下面只考虑起点。

由于起终点之间的方案数就是 $\frac{\binom{2len}{len}}{len+1}$ 的形式，我们钦定这部分全部在斜线上面走。那折线就变成了 $(0,0)$ 到起点且只在起点触碰斜线 乘上 起点到 $(n,n)$ 并且不穿过斜线。

这样也是两个 $(0,0)\to (a,b)$ 不触碰 $y=x+(b+1-a)$ 的形式，可以把两段折线拼起来，贡献是两个组合数相减。

再枚举所有的 $k$ 加起来，发现是要求若干个如下的形式：

$$\sum_{k=0}^{m-n}\binom{2p+k}{p}\binom{n+m-k-2p}{n-p}$$

观察一下，发现上面加起来是常数，下面加起来也是常数。把这个看作要求 $\sum_{i=l}^{r} \binom{i}{k}\binom{n-i}{m-k}$。

先差分成求 $\sum_{i=0}^{r} \binom{i}{k}\binom{n-i}{m-k}$。若移动起点 $p\to p+1$，则 $n,m$ 不会修改，$r,k$ 有 $O(1)$ 的变化量，则这个式子可以 $O(1)$ 维护：

• 增大 $r$ 显然只需要加上一项。
• 增大 $k$ 的话，考虑这个式子的组合意义是“在 $n$ 个白球中染黑 $m$ 个，且第 $k$ 个黑球的位置 $\le r$”。若 $k\to k+1$，则限制变成“第 $k+1$ 个黑球的位置 $\le r$”，需要减去第 $k+1$ 个黑球位置 $> r$ 的情况。

于是这部分也能做到 $O(n)$。