[清华集训2016] 你的生命已如风中残烛

刚刚学完 Raney 引理，写道例题和题解帮助理解。

前置知识：Raney 引理，卡特兰数。

思路简析

首先我们需要知道，什么样的牌堆不会断抽会赢。

我们定义每张牌的牌效为：打出这张牌后，手中卡牌数量的变化量。

那么特殊牌的卡效为 w_{i}-1，普通牌的牌效都是 -1。

我们把所有牌的牌效都按顺序存入 w 序列中。

定义：s_{i}=\sum w_{i}

我们不断抽的条件显然就是 \forall~i\in [1,n),~s_{i}\ge 0。

并且 s_{n}=-1 ，毕竟你把所有抽到的牌都可以打掉，一张不剩。

而 Raney 引理：

设整数序列 \{A_{i}\}，\sum A_{i} =1

有且仅有一个整数 x，满足对 A_{x},A_{x+1},A_{x+2}\dots A_{1},A_{2},\dots A_{x-1} 求前缀和 s_{i}，使得 \forall s_{i} >0 。

不幸的是，我们会发现原题中 s_{i} 可以 =0，无法直接使用引理。

但是我们可以发现，对这个序列任意求前缀和必定为非负，等价于求后缀和必定为负数。

证明： s_{n}=-1 \to s_{k}+s_{n}-s_{k}=-1

又因为 s_{k} \ge 0，所以 s_{n}-s_{k} <0。

那么我们把整个序列取反，再翻转。我们就可以发现现在的序列 \{A_{i}\}，既满足 \sum w_{i}=1，也满足 \forall s_{i}>0。这下就可以使用引理了。

根据引理，每个圆排列都只会对答案有一个贡献，而我们需要保证 w_{n}=-1。

答案数就是 \frac{m!}{m-n+1}，分母直接套用圆排列，分子是因为从 m-n+1 个 -1 中任意选一个放在最后都等价，所以要除掉重复的。

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+5;
const ll mod = 998244353;
inline ll read(){
    ll x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
ll n,m;
ll w[N];
ll qpow(ll x,ll b){
    ll res=1;
    while(b){
        if(b&1) res=res*x%mod;
        x=x*x%mod;
        b>>=1;
    }
    return res;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++)w[i]=read(),m+=w[i];
    ll ans=1;
    for(int i=2;i<=m;i++)ans=ans*i%mod;
    cout<<ans*qpow(m-n+1,mod-2)%mod<<'\n';
    return 0;
}