一则求总贡献的例题——联考题引发的思考-526互联

对于一些求总贡献的题，与许多人的常识相反，直接求期望往往比求总和更容易. 以今天联考 T1 的一个环节为例.

【例】对排列 \(P_n\)，定义 \(C(P_n):=\left|\{i:P_j>P_i,\ \forall j<i\}\right|\)，即其前缀最小值序列的不同数个数. 给定 \(n\)，求全部 \(n!\) 个排列 \(P_n\) 的 \((-1)^{C(P_n)}\) 之和.

【解】设所求答案为 \(n!E_n\)，则 \(E_n\) 是期望值. 不难写出递推式

\[E_n=-\dfrac1n\sum_{i=1}^nE_{i-1},\ \forall n\in\mathbb{N}^*, \]

其含义是枚举第一个位置放 \(i\)，贡献一个因子 \((-1)\) 并覆盖后面 \(>i\) 的数，相当于只有 \(<i\) 的数有贡献.

初始条件为 \(E_0=1\)，可得 \(E_1=-1\)，恰好抵消，因此后面都是 \(E_i=0\). 这就解决了本题.

如果你不喜欢猜答案，也可以正儿八经地去解这个递推式，并不复杂.

由于 \(\dfrac1n\) 不好处理，我们把 \(n\) 乘到左边（这样同时使递推式成立的范围扩大了）：

\[nE_n=-\sum_{i=0}^{n-1}E_i,\ \forall n\in\mathbb{Z}. \]

对 \(n\ge0\)，两边取差分得

\[(n+1)E_{n+1}-nE_n=-E_n,\ \forall n\in\mathbb{N}^*, \]

即

\[E_{n+1}=\dfrac{n-1}{n+1}E_n,\ \forall n\in\mathbb{N}^*. \]

当初值为 \(E_0=1\) 时 \(E_1=-1\)、\(E_2=0\)，后面便都是 \(0\).

当然，既然 gf 可解万物，为什么不试试呢（

对乘过 \(n\) 的递推式取 gf，两边分别化简得

\[zG'(z)=-\dfrac{z}{1-z}G(z), \]

即

\[G'(z)+\dfrac1{1-z}G(z)=0. \]

这是个一阶齐次线性微分方程，将其化为

\[\dfrac{G'(z)}{G(z)}=\dfrac1{z-1} \]

即

\[\left(\ln G(z)\right)'=\dfrac1{z-1} \]

两边积分有

\[\ln G(z)=\int\dfrac1{z-1}\mathrm{d}z. \]

右边的积分等于 \(\ln(z-1)+C_0\)，所以 \(G(z)=C_1(z-1)\). 再利用 \(G(0)=E_0=1\) 得到 \(G(z)=1-z\).（这里函数取值是否有意义其实是有问题的，但并不妨碍我们求得结果.）

仅供娱乐，毕竟 OI 考场上解微分方程实在有点喜感（

另一个例子是 xcs 的远古模拟赛题，可转化为求解

\[E_n=1+\dfrac1n\sum_{i=1}^nE_{i-1}. \]

与本题如出一辙.