题意

给你m个数，问有多少种排列方式使得每一个前缀和都不小于0。 m≤4∗106 m ≤ 4 ∗ 10 6

分析

我之所以这样子转化题目，是先让除了第m+1个0以外，每个数都减去1，这样的话前缀和表示的就是当前还能再抽几张卡。但因为第一张卡不消耗抽卡次数，所以要把每个前缀和都加上1。 我们考虑在最后面添加一个-1，那么现在问题就变成了有多少种排列使得除了最后一位以外其余前缀和都不小于0。 这里有一个结论，就是在所有循环同构的排列中，有且仅有一个是合法的。 为什么呢？考虑一个合法的排列，除了最后一个前缀和是-1，其余前缀和都不小于0。也就是说，所有后缀和都是不大于-1的。那么当我把它往后移若干位后，某一个后缀就变成了现在的前缀，也就是某一个前缀必然小于0，所以不合法。 对于某个不合法的排列，我找到它最小的前缀和中最靠后的一个，然后把这个位置作为最后，这样就可以得到一个合法的排列了。 注意到圆周排列的数量是 m! m ! ，且最后一个-1的种类固定，所以答案就是 m!m−n+1 m ! m − n + 1 。

代码

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> typedef long long LL; const int MOD=998244353; int n,m; int main() { scanf("%d",&n); for (int i=1,x;i<=n;i++) scanf("%d",&x),m+=x; int ans=1; for (int i=1;i<=m;i++) if (i!=m-n+1) ans=(LL)ans*i%MOD; printf("%d",ans); return 0; }