分析
转化一下条件,就是 \(\sum{w_i}\geq i\),将所有牌权值减一,那就是 \(\sum{w'_i}\geq 0\)
根据Raney引理,总和为 1 的数列,在循环移位时,只有一种情况所有前缀和都为正数
那么只要构造出一个长度为 \(n\) 数列,总和为 1,那么它的答案就是 \((n-1)!\)
考虑在前面补一个 1,但是它并不能保证 1 一定在最前面。
那么将所有牌权值取反并翻转,可以发现现在可以在前面补 1,因为 1 一定是最大的,
所以只要钦定补的 1 在最前面,一共有 \(m-n+1\) 个 1,数列长度为 \(m+1\)
所以最终的答案为 \(\frac{m!}{m-n+1}\)
代码
#include <iostream>
using namespace std;
const int mod=998244353;
int n,m,ans=1;
int main(){
ios::sync_with_stdio(0);
cin>>n;
for (int i=1,w;i<=n;++i) cin>>w,m+=w;
for (int i=2;i<=m-n;++i) ans=1ll*ans*i%mod;
for (int i=m;i>m-n+1;--i) ans=1ll*ans*i%mod;
cout<<ans;
return 0;
}