#Raney引理,圆排列#洛谷 6672 [清华集训2016] 你的生命已如风中残烛

题目


分析

转化一下条件,就是 \(\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;
}
上一篇:下降幂多项式的简单小应用


下一篇:ARC135 题解