旋转序列
来源：
两个串之间 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)，然后差分即可。
交换豆子
来源：
假设 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)。
序列计数
来源：
考虑转化成一个格路计数问题：
- 有一个 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)。
