题解 P6672 【[清华集训2016] 你的生命已如风中残烛】

感觉有些东西题解讲的迷啊，而且都比较简略……希望这篇题解能把这道神题所有点讲清楚qwq --- **Step 1 问题转化** 如果我们把每个数都减去 1 （$a_i=w_i-1$），显然不影响答案，但是我们对于每个 $i$ 都要满足的约束条件就相同了，因为每个数的限制变成了 $\forall i\in[1,m] \sum_{j=1}^{i}a_j\ge 0$，即所有数的和为 $0$，要求每个前缀和都为非负数。 --- **Step 2 Raney 引理** 读过《具体数学》的会知道有这样一个引理（Page 301） > 如果 $x1,x2,...,x_m$ 是任何一个和为 1 的整数数列，则其所有循环位移中恰好有一个满足所有的前缀和都是正数。 这个是 Raney 引理。证明方法也比较简单，此处不另行证明。 我们还可以让它看上去简单一些（方便计数） > 对于一个环 $x1,x2,...x_m$ 满足 $\sum x=1$，则破环为链后形成的 $n$ 种可能的链，只有一个链满足所有前缀和为正数。 所以，假设 $m$ 个数数之和为 $1$，那么满足使得所有前缀和为正数的排列的数量即其**圆排列**的数量 $(m-1)!$，因为每个圆排列（环）都只有一个链满足条件。 **Step 3 返回原题** 原题中说的是 $\sum a_i$ 为 $0$，并且前缀和为非负整数。所以我们不能直接这样做。 《具体数学》中有一个例子，有多少由 $n$ 个 $+1$ 和 $n$ 个 $-1$ 组成的数列满足所有前缀和 $\ge 0$。这道题有个很妙的技巧，就是我们在最前面多加一个元素 $a_0=+1$，这样就能满足和为 1 且前缀和都是 0 了。 那这道题能不能用相同的方法呢？答案是不能。比如这个例子 $\{2,-1,-1\}$。假如我们加进去一个 $1$，变成 $\{1,2,-1,-1\}$。圆排列数量为 $6$，但答案应该是 $1$。问题出在哪里？ 考虑两个合法方案 $\{2,-1,-1,1\}$ 和 $\{2,-1,1,-1\}$。当我们把事先加进去的 $1$ 给拆出来后，得到的两个方案数相同的。其本质原因在于，$1$ 不一定顶在首位。在上个题中，$1$ 能拆出来的原因是 $1$ 无论如何都会排在数列的最前端，我们能够很 eazy 的拆掉这个 $1$ 并计算剩下的值。但这道题中，存在 $1$ 不是排列的第一个的情况，于是和我们一开始的假如 “我们在最前面加进去一个 $1$”矛盾，产生了问题。（感觉这个解释可能容易理解很多？） --- 我们知道了我们不能拆成 $1$，因为有 $>1$ 的数存在，会抢走 $1$ 的最前端位置。那么有什么数是不会遇到这种情况的呢？-1！我们在末尾加上一个 -1，要求前 $m$ 个前缀和都是非负数，这样就可以保证排列的末尾一定是 $-1$。至于怎么说明这种方法的正确性，有两种解释。 第一种解释就是其他几篇题解的解释。 第二种解释为，我们在末尾加上 -1 后，让所有数（包括这个-1）取反，然后再逆序一下，就有：有多少排列满足所有前缀和都为正数，且最前端为 $1$，和Raney引理中一样。此时没有比 $1$ 更大的数了（因为原来最小的数是-1，取反后变为1）。  然后我们有排列的数量=圆排列的数量=$(m+1-1)!=m!$。 最后除掉我们这个加上的 $-1$ 所带来的影响。原本一共有 $m-n$ 个 $-1$，排列数为 $(m-n)!$，但是现在加上了这个 $-1$ 后有了 $n-m+1$ 个，排列数为 $(m-n+1)!$，比之前多乘了 $(m-n+1)$。 所以我们有 $$ ans=\frac{m!}{m-n+1} $$ 希望本题解能让你对 Raney 引理以及组合计数有更深的理解！ ```cpp #include<bits/stdc++.h> #define int long long #define rep(i,a,b) for(register int i=(a);i<=(b);i++) #define per(i,a,b) for(register int i=(a);i>=(b);i--) using namespace std; const int mod=998244353; inline int read() { register int x=0, f=1; register char c=getchar(); while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();} while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();} return x*f; } signed main() { int n=read(),m=0,ans=1; rep(i,1,n) m+=read(); rep(i,2,m) ans=ans*(i==m-n+1?1:i)%mod; printf("%lld\n",ans); return 0; } ```