哑演算初探

[哑演算（Umbral Calculus）](https://en.wikipedia.org/wiki/Umbral_calculus)，或称本影演算、Blissard 演算，是一种进行恒等式推导时的技术手段。它的内涵是相当丰富的，我仅谈谈我在几乎仅了解定义的情况下尝试使用它，得到的一些收获。 在进行一些题目推导时，我确实发现这种方法能很大程度上简化步骤，并且结合转置原理或许事半功倍。 究竟是什么技术呢？一句话解释，就是我们把一个数列 $A_n$ 在推导过程中直接写成 $t^n$。 让我们来简单看两道集训队自选题，感受一下上述方法是如何使用的： > **小 Y 的序列**（yht） 给出正整数 $n, w$，对于每个 $1\le k\le n$，求出 > $$ \sum_{\{1\le a_i\le w\}_{i=1}^n} \# \left\{ i \middle \vert \exists i_1<i_2<\dots <i_k, a_{i_j} < a_i \right \} $$ > 同余 $998244353$，保证 $1\le n\le 114514, 1\le w\le 114514191$。 首先考察题设的 $\exists$ 条件，我们不如先数出最大的 $k$，然后做一个后缀和即可。 先转成随机生成然后数期望，我们接下来分别考虑答案的 GF，当 $a_{i+1}=j+1$ 的时候，前面每个数有 $\frac jw$ 的概率给 $k$ 加一。 $$ \begin{aligned} &\quad \frac 1w\sum_{i=0}^{n-1} \sum_{j=0}^{w-1} \left(\frac {w-j}w + \frac jw x\right)^i\\ &= \frac 1w\sum_{i=0}^{n-1} \sum_{j=0}^{w-1} \left(1 - \frac jw + \frac jw x\right)^i \end{aligned} $$ 我们考虑令 $t^k$ 替换掉 $\sum_{j=0}^{w-1} \left(\frac j w\right)^k$，此时有 $$ \begin{aligned} &= \left[\frac 1w\sum_{i=0}^{n-1} \left(1 - t + t x\right)^i\right] \\ &= \left[\frac 1w \cdot \frac{1 - \left(1 - t + t x\right)^n}{1 - \left(1 - t + t x\right)} \right] \\ &= \left[\frac 1w \cdot \frac{1 - \left(1 - t + t x\right)^n}{t(1-x)} \right]\\ &= \frac 1{w(1-x)} \cdot \left[\frac{1 - \left(1 - t + t x\right)^n}{t} \right] \\ &= \frac 1{w(1-x)} \cdot \left[\frac{1 - \left(1 - t\right)^n}{t} - \sum_{j=1}^n \binom n j (1-t)^{n-j}t^{j-1} x^j \right] \\ \end{aligned} $$ 在结合计算时进行的哑元推导，我们只需时刻思考：一个 $t$ 构成的多项式族所代表的实际数列是不是可以快速计算？我们首先可以用 Bernoulli 数在 $\Theta(n\log n)$ 时间内计算出每个 $t^k$。而再计算出每个 $(1-t)^{n-j}t^{j-1}$ 就成了，将其展开，是一次卷积。 刚刚的问题可能较为简单，不够有说服力，我们来看一个稍微复杂一点的问题中，如何使用这种方法： > **Game On a Circle II**（yzr） 给定长为 $n$ 的排列 $a$ 和概率 $p$。一个指针从 $1$ 开始顺时针走，每次有 $p$ 的概率将当前数删掉加入到序列 $b$ 的末尾。过程直到整个序列被清空，得到排列 $b$。问 $b$ 的**康托展开值**的期望。 > 同余 $998244353$，保证 $n\le 5\times 10^5$，$\operatorname{ord} (1-p) > n$。 首先注意到康托展开值是拆成各位之和的，而第 $i$ 位的贡献就是 $| b_i>b_j \land i < j |$ 乘以 $(n-i)!$。 那么一个朴素的想法就是先枚举每个 $a_i$，看看其在序列 $b$ 中出现在位置 $j$ 的概率乘以此时 $| b_i>b_j \land i < j |$ 的期望。根据期望的线性性，我们拆解为对每个 $a_i>a_k$，统计「$a_i$ 在第 $j$ 轮被删去，且此时 $a_k$ 仍存活」的概率。 这里有一个重要的转化，就是将问题转换为一个无穷和进行计算，我们认为一个数被“删掉”是做了至少一次标记，那么设 $q=1-p$，我们可以尝试先写出在第 $k$ 轮 $a_i$ 被删除，此时其对答案的贡献，可以预见这个式子是一个关于 $q^k$ 的多项式，我们求和会得到 $\sum_{k\ge 0} q^{jk} = \frac 1{1-q^j}$，而这种东西的处理是棘手的，所以我们可能务必需要得到 $q^{jk}$ 项系数。具体来讲，对于 $a_i$，如果我们考虑其左边的一个数晚于它被删去，那么在第 $k(\ge 0)$ 轮，可以枚举剩余的数被删去的情况： $$ \sum_{l=0}^{i-2} \sum_{r=0}^{n-i} \binom {i-2}l \binom{n-i}r (n-l-r-1)! \cdot (1-q^{k+1})^l (1-q^k)^r \cdot q^{(k+1)(i-1-l)} q^{k(n-i-r)} \cdot pq^k $$ 设 $t=q^k$，这是自然的，因为我们最后就会直接将 $t^k$ 变成 $\frac 1{1-q^k}$。有 $$ \begin{aligned} & = \sum_{l=0}^{i-2} \sum_{r=0}^{n-i} \binom {i-2}l \binom{n-i}r (n-l-r-1)! \cdot (1-qt)^l (1-t)^r \cdot {(qt)}^{i-1-l} t^{n-i-r} \cdot pt\\ & = p\cdot \sum_{l=0}^{i-2} \sum_{r=0}^{n-i} \binom {i-2}l \binom{n-i}r (n-l-r-1)! \cdot (1-qt)^l (1-t)^r \cdot q^{i-1-l} t^{n-l-r} \end{aligned} $$ 我们将 $(n-l-r-1)!$ 代换成 $u^{n-l-r-1}$，那么这个式子可以直接根据二项式定理合并。 $$ \begin{aligned} & = p\cdot \sum_{l=0}^{i-2} \sum_{r=0}^{n-i} \binom {i-2}l \binom{n-i}r u^{n-l-r-1} \cdot (1-qt)^l (1-t)^r \cdot q^{i-1-l} t^{n-l-r}\\ & = p u^{n-1} q^{i-1} t^n\cdot \sum_{l=0}^{i-2} \sum_{r=0}^{n-i} \binom {i-2}l \binom{n-i}r u^{-l-r} \cdot (1-qt)^l (1-t)^r \cdot q^{-l} t^{-l-r}\\ & = p u^{n-1} q^{i-1} t^n \left( 1 + \frac{1-qt}{uqt} \right)^{i-2} \left( 1 + \frac{1-t}{ut} \right)^{n-i}\\ & = pq u t^2 \left( uqt + 1-qt \right)^{i-2} \left( ut + 1-t \right)^{n-i}\\ & = pq u t^2 (1+qt(u-1))^{i-2} (1+t(u-1))^{n-i} \end{aligned} $$ 我们令 $v^{\bullet}=u(u-1)^{\bullet}$（注意 $v$ 可以通过微分方程在线性时间内计算，因为 $u$ 是特殊数列），也就有 $$ = pq t^2 (1+qtv)^{i-2} (1+tv)^{n-i} $$ 我们又注意到一个重要性质，这里 $t,v$ 是绑定在一起出现的，可以令 $t^2(tv)^\bullet = x^\bullet$，也就有 $$ = pq (1+qx)^{i-2}(1+x)^{n-i} $$ 我们要对所有的 $i$ 都求出，因此转置问题就是计算 $\sum_i a_i pq (1+qx)^{i-2}(1+x)^{n-i}$，这是显然可以 $\Theta(n\log n)$ 的，不同的变形方法都可以得到结果。处理另一半的式子大同小异，在此不予重复。 原解法的这一步是通过对一个简化的组合问题进行观察，得到的最初变形方向。而在我们借助哑演算的基础上，一切性质都浮现得自然而然。