BZOJ4735 你的生命已如风中残烛（组合数学）

　　将每个位置上的数都-1，则显然相当于前缀和始终非负。

　　然后就是完全想不到的了。考虑往里面加一张-1的牌。假设在一个合法排列的最后添上一个-1，那么在该排列的所有循环同构排列中，满足前m个前缀和都非负的排列只有原合法排列，因为如果更换开头的话显然有s-s<=s<0。并且对于每一种循环同构排列，都存在一个满足前m个前缀和都非负的排列，因为只要取最小前缀和的后一个为开头即可，证明类似。这样的排列去掉最后一个数就对应了一个合法排列，而显然这样的排列个数就是循环同构排列的种类数，也即m!。同时每一张-1牌都可能位于末尾，而不管是哪张，对应的合法排列可以看成相同的，所以再除以(m+1-n)。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 42

#define P 998244353

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,m,a[N],ans=;

int inv(int a)

{

    int s=;

    for (int k=P-;k;k>>=,a=1ll*a*a%P) if (k&) s=1ll*s*a%P;

    return s;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj4735.in","r",stdin);

    freopen("bzoj4735.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read();

    for (int i=;i<=n;i++) m+=(a[i]=read())--;

    for (int i=;i<=m;i++) ans=1ll*ans*i%P;

    cout<<1ll*ans*inv(m+-n)%P;

    return ;

}