出征

P16689 出征 - 洛谷

给出一个序列 $a_i$，和常数 $p$，你可以进行若干次操作，每次操作可以选择一个 $j$，使得 $i \in [j, n]$ 的后缀中，统一增加或减少 $\binom{i - j + p}{p}$。问至少多少次操作之后才能将序列全化为 $k$。

$1 \le n \le 10 ^ 5, 0 \le p \le 80, 0 \le k, a_i \le 10 ^ 6$。

对于这个题，还是很神奇的，实际上不是计数题。

我们可以先观察特殊性质，发现 $p = 0$ 的时候，就是选一个后缀，使得这个后缀统一增加或者减少 $1$，那这个我们是怎么做的呢，我们显然是可以从前往后判断，逐个满足每一个的要求，我们写暴力的时候发现，其实如果你在 $j$ 点进行了一次操作，其实不是很影响这个序列，不需要修改，只需要打上一个标记，后面的标记推下去计算即可。

于是我们就想到，是否操作只和单点有关，我们发现对于 $p = 0$ 的时候，我们将这个增加的贡献表达出来就是 $f(j) = [0, 0, 0, \dots, 1 ,1 ,1 , \dots]$，对于这个增加的贡献，我们可以对其做一次差分，得到的差分序列 $\Delta ^1 f(j) = [0, 0 ,0 ,\dots 1, 0, 0, \dots]$，发现进行一次差分之后，就变成与 $j$ 点相关的单点修改操作了。

具体的来说，我们每一次对选择的 $j$，后缀的增加或减少都是呈现 $f(j) = [0, 0, 0, \dots, \binom{p}{p}, \binom{p + 1}{p} , \binom{p + 2}{p} , \dots]$，这样的增加贡献，我们再考虑刚刚的差分操作，也就是，第一个位置不变，为 $\binom{p}{p}$，第二个位置是 $\binom{p + 1}{p} - \binom{p}{p} = p = \binom{p}{p - 1}$。这个部分实际上还可以用帕斯卡三角直接转化，因为 $\binom{p + 1}{p} = \binom{p}{p} + \binom{p}{p - 1}$，因此，移项就能得到。后面的同理，我们发现实际上一次差分会使得上下指标减 $1$，对于第一项，我们就可以把 $\binom{p}{p}$ 写成 $\binom{p - 1}{p - 1}$。我们可以写出通用式子的一阶差分 $\Delta^1 f(j) = [0, 0, 0, \dots, \binom{p - 1}{p - 1}, \binom{p}{p - 1}, \binom{p + 1}{p - 1}, \dots]$。很明显这个式子还能继续做差分，我们想要的是把这个变成单点的修改操作，这样就和 $p = 0$ 做一阶差分时的统计方式是一样的。

我们考虑只有经过 $p$ 轮，这样组合数选的就是 $0$，也就是又变回了我们的最初的 $p = 0$ 的情况，我们只需要再做一轮差分，就能得到最终我们想要的单点的修改贡献，即：

$$ \Delta ^ {p + 1} f(j) = [0, 0, 0, \dots, 1, 0, 0, \dots] $$

这样的式子，我们就可以清晰的看到具体哪个地方进行了操作。

因此我们的最终做法是，先把原数组 $a_i \gets k - a_i$，这样只需要判断到 $0$ 即可，对 $a_i$ 做 $p + 1$ 次差分，最后答案就是 $\sum |a_i|$。

为什么要开 int128 ？

我们考虑差分操作，对于 $\Delta ^ 1 a_i = 1\times a_i - 1\times a_{i - 1}$，对于 $\Delta ^ 2 a_i = 1 \times a_i - 1 \times a_{i - 1} - (1 \times a_{i - 1} - 1 \times a_{i - 2}) = 1 \times a_i - 2\times a_{i - 1} + 1\times a_{i - 2}$。

重复这个过程，我们发现其形态类似于二叉结构，每一个 $a_i$ 在做贡献时，都会在自己和前面的位置做一次贡献，这实际上就是帕斯卡三角的系数问题。

因此对于连续的 $p + 1$ 次，我们 $a_{i - j}$ 的贡献系数就是 $(-1) ^ j \binom{p + 1}{j}$，对于最坏的情况，我们把所有绝对值加起来，即 $\sum \binom{p + 1}{j} = 2 ^ {p + 1}$，因此对于 $2 ^ {81}$ 可以证明 int128 是可以存下的。