题解 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 引理以及组合计数有更深的理解！

#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;
}