自动搬运

查看原文

来自洛谷，原作者为

	lgswdn_SA 舞台少女，每日进化中

搬运于2025-08-24 22:22:58，当前版本为作者最后更新于2021-01-27 22:50:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

感觉有些东西题解讲的迷啊，而且都比较简略……希望这篇题解能把这道神题所有点讲清楚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)$。

所以我们有

希望本题解能让你对 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;
}