P6672 [清华集训 2016] 你的生命已如风中残烛题解 & Raney 引理及其证明与应用

· · 题解

本篇文章用于提交洛谷 P6672 的题解与证明 Raney 引理和介绍其主要应用，熟悉该引理与应用的同学可以直接跳跃到本篇文章的【练习】板块。

Raney 引理及其证明与应用

定义

引理内容：对于 n 个整数 x_1,x_2,\dots,x_n，定义 sum_i=\sum\limits_{j=1}^{i}x_i，若有 sum_n=1，则其所有循环位移中有且只有一个满足 \forall i,sum_i>0。

证明

下文为图简易明了，使用 sum\{i,j\} 表示 \sum\limits_{k=i}^{j} x_k。此写法并不规范，慎重模仿。

首先证明存在性。

考虑使用反证法。假设不存在任何满足上述要求排列方式的序列，那必然对于任意一个排列方式的序列，都存在最后一个不满足的点。于是不妨随意选出一个排列方式，将其标号为 1,2,3,\dots,n，设其最后一个不满足的点为 m_1。自然说明 sum\{1,m_1\} \leq 0,sum\{m_1+1,n\} \geq 1。

从点 m_1+1 开始，向后寻找最后一个不满足的点（前缀和也从 m_1+1 点开始累加），将其标记为 m_2（以我们最初随意选的序列为标号标准），显然 m_2 在 m_1 前面。因为 sum\{m_1+1,n\}+sum\{1,m_2\} \leq 0，所以得出 sum\{m_2+1,m_1\} \geq 1。

同样的，从点 m_2+1 开始，向后寻找最后一个不满足的点，标记为 m_3，显然 m_3 在 m_2 前面。因为 sum\{m_2+1,n\}+sum\{1,m_3\} \leq 0，所以得出 sum\{m_3+1,m_2\} \geq 1。

以此类推。

于是发现整个序列被各个区间内的 sum\{i,j\} \geq 1 布满了，只有第一个数有点存疑，不是很好想。但是考虑将其移到最后，整个序列必然合法。

于是，我们在假设不存在任何满足上述要求排列方式的序列的情况下，找到了一个合法序列。假设错误，得出必然存在合法序列。

然后证明唯一性。

使用反证法。不妨假设有两个满足上述要求的排列方式，不妨以其中一个序列来看，设另一个符合要求的序列的开头在本序列中的第 m 项。

由于本序列合法，自然有 sum_{m-1}+sum\{m,n\}=sum_n=1，而 sum_{m-1}>0，则有 sum\{m,n\} < 1，由于 x_i 均为整数，自然有 sum\{m,n\} \leq 0，而考虑到另一个以 m 开头的序列，因其合法，于是要求 sum\{m,n\} > 0，显著矛盾，假设错误，得出不存在两个及以上合法的序列。

证毕。

特别的，唯一性的证明是我的母亲提出的。

应用

推导卡特兰数通项公式

不妨将 ( 看做是 +1 ，将 ) 看作是 -1 ，设括号序列为 x_1,x_2,\dots,x_{2n}，显然 \sum\limits_{i=1}^{2n}=0。所有前缀和必然 \geq 0。

如何使用 Raney 引理推导？考虑将序列最前部加上 (，于是其总和变为 1，前缀和的条件于是变为 > 0。

随意填的方案数为 \begin{pmatrix} 2n+1 \\ n \end{pmatrix}，根据 Raney 引理，2n+1 个数随便循环位移，其中只有一个能满足条件，于是合法方案数为 \frac{\begin{pmatrix} 2n+1 \\ n \end{pmatrix}}{2n+1}=\frac{\begin{pmatrix} 2n \\ n \end{pmatrix}}{n+1}。

练习

洛谷 P6672 [清华集训 2016] 你的生命已如风中残烛

题解

题意简述

有 m 个数 a_1,a_2,\dots,a_m，求使得 \forall i,\sum\limits_{j=1}^{i}a_j-i \geq 0 的排列数量。特别的，\sum\limits_{i=1}^{m}a_i=m。

题目转化

为了使所有数的要求不受到下标的影响，首先令所有数 -1。这样要求就是 \forall i,\sum\limits_{j=1}^{i}a_j \geq 0。那么此时特别的为 \sum\limits_{i=1}^m a_i=0。

看到一段和 \geq 某个数，整体总和还 = 某个数的话，自然想到 Raney 引理相关的。考虑如何化成 Raney 引理的形式。

引理转化

发现我们要求的都要比 Raney 引理小 1，那我们尝试像我们之前推导的卡特兰数通项公式一样，在整个序列的最开头加上一个 1，是不是就是和 Raney 引理一样了？

并不是。因为这个序列中还有许多其他的数，我们不怕有许多个 1，因为以后还可以慢慢往下除，但是怎么敢保证我们自己加的 1 就是最小的那个？保证不了。

那怎么办，我怎么保证我加进去的是最小的？

那自然是负数。

考虑在末端加入一个 -1，整体取反，再进行取后缀和（相当于序列反转后计算前缀和）。因为这里取反以后我们最小的就只有 1，就可以保证我们加进去的 -1（取反后为 1）排在最前方（因为序列翻转）。

具象化一下上面的过程。

于是我们将它化为了 Raney 引理的形式。

答案处理

所有可能排列方式自然为 \frac{(m+1)!}{m+1}=m!。但是考虑到我们原来的序列中也有其他经过 -1，取反后得到 1 的，因此 1 的贡献算重复了。考虑原序列中一共有 m-n 个 0（只有 0 经过上述操作才会变为 1），加上我们自己新加的一个，共有 m-n+1 个，于是答案除以 m -n+1。

最终结果即为 \frac{m!}{m-n+1}。

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
int n , num , ans = 1;
signed main()
{
    scanf("%lld" , &n);
    for(int i = 1 , a ; i <= n ; i ++) scanf("%lld" , &a) , num += a;
    for(int i = 1 ; i <= num ; i ++) ans *= ((num - n + 1 == i) ? 1 : i) , ans %= mod;
    printf("%lld" , ans);
    return 0;
}