P6672 你的生命已如风中残烛

我的生命已如风中残烛...

思维好题 问题等价于\(m\)个数和为0, 求所有前缀和都不小于零的排列的个数.
将所有权值 \(-1\) 就可以了.
可以在最后添加一个\(-1\), 这样就是求前\(m\)个大于, 把排列连成环, 这样就有一个很好的性质, 每个圆排列只有一种断开的方法.
这个画个图比较好理解, 假设当前已经是合法的方案, 左右移动一下再断开都是不合法的.
圆排列的排列数是\(m!\), 因为\(-1\)要钦定一个, 所以除以\(-1\)的个数.
最后答案就是\(\frac{m!}{m+1-n}\)

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
int n, m, x;

int main() {
	int res = 1;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &x), m += x;
    for (int i = 1; i <= m; i++) if (i != m - n + 1) res = res * 1ll * i % MOD;
    printf("%d\n", res);
    return 0;
}