BZOJ4735

Description

众所周知，萌萌哒六花不擅长数学，所以勇太给了她一些数学问题做练习。但是今天六花酱不想做数学题，于是他们开始打牌。现在他们手上有 张不同的牌，牌有两种：普通牌和功能牌。功能牌一共有 张，每张功能牌都有一个属性值 ，保证 现在勇太将这 张牌随机打乱（一共有 种不同的顺序）。一开始，六花先从牌堆顶端取一张牌。接着每回合六花可以选择手中的一张牌打出，如果这张牌是普通牌，那么什么都不会发生；如果这种牌是功能牌，那么六花需要从牌堆顶端再取 张牌。重复这个过程直到六花手中没有手牌或六花要摸牌的时候牌堆已经空了，如果是前者，则勇太胜利，否则六花胜利。举例来说，如果牌堆是 {3，0，2，0，0）（用 0 表示普通牌，其他数字表示 ），那么六花打牌的过程可以为： 1) 取一张牌，手中的牌为 {3}。 2) 打出 {3}，再取三张牌，手中的牌为 {0，2，0}。 3) 打出这三张牌，还需要再取两张，取到第二张的时候牌堆中已没有牌，六花胜利。 而如果牌堆是 {2，0，0，3,0}，不难发现是勇太大胜利。现在，六花想要知道，这 M! 种顺序中，有多少种是能让自己取得胜利的呢。当然这个问题对萌萌哒六花来说实在是太雉了，所以她来向你寻求帮助，你能帮帮她吗。

Input

第一行一个整数$ nn$他个空格隔开的正整数 。 通过输入你可以自己算出来 ### Output 输出一个整数表示答案，答案可能很大，你只需要输出对 998244353 取模后的结果。

Sample Input

1
3

Sample Output

2

Hint

m! 种牌堆中，{3，0，0），{0，3，0）{0，0，3）各有两个，其中只有第一种满足条件。

Solution

神仙JMR推荐的神仙题，考场上遇到直接暴力走人...

再想到从顶端取牌相当于每次还可以摸的牌数，遇到一个特殊牌即可以多摸那么多张牌，记录下这个“还可以摸的牌数”就会发现，这个数（每张牌对应一个数，下同）的排列中，把每个数都好像是要求所有前缀和都大于等于。

好像卡特兰数但一仔细看是正数和不是和。所以GG

正解的话观察样例每个数都减一后形成的数列它的总和为零(废话) 于是可以在最后补一个即求除最后一项以外其他前缀和都大于的方案数，对这个数环排列(共种方案)每种环排列钦定这个多出来的放最后所以每种排列只有唯一对应的方案。

会发现有些方案重复计算了，具体是哪些呢，比如在第个处都被算了一遍所以方案要除以的个数即普通牌数加钦点的那张牌，也即是牌总数-功能牌数+钦点的的那张牌 所以答案表达式 十分简短沙雕 ### Code

#include<bits/stdc++.h>
#define FIO "4735"
#define INF 0x3f3f3f
typedef long long ll;
const int MOD=998244353;
using namespace std;
char buf[1<<20]; int bufl,bufr;
#define getch ((bufl^bufr||(bufl=0,bufr=fread(buf,1,1<<20,stdin)))?buf[bufl++]:EOF)
template <class T>inline void read (T &x) {
	T f=1;
	x=0;
	char ch=getch;
	for (; !isdigit (ch)&&ch!='-'; ch=getch);
	if (ch=='-')f=-1,ch=getch;
	for (; isdigit (ch); ch=getch)x=x*10+ch-'0';
	x*=f;
}
int N,M,ans=1,x;
int main() {
	read (N);
	for (int i=1; i<=N; i++)read (x),M+=x;
	for (int i=1; i<=M; i++)if (i^M-N+1)ans= (ll)ans*i%MOD;
	printf ("%d\n",ans);
	return 0;
}