清华大学生命科学博士就业_已拥有的是全部的生命

大家好，又见面了，我是你们的朋友全栈君。

不错的组合数学题。同时这也驱使我去看积灰好久的《具体数学》（看了yu大的blog后）。然后看得头秃……

得到一个不等式前缀和大于等于取了的个数。所以如果把每个卡的值减一，问题就变成了求一个排列，使得前缀和都非负。

\[\forall i, \mathbf{s.t.} a_1 + a_2 + \dots + a_i \geq 0 \]

显然 \(\sum a_i = 0\)

看样子很难搞。

可以发现，如果把序列循环位移，可能会得到新的方案，那么对每个环进行计算。

但是环可能会贡献多个值，如果这么做，答案就是 \(\sum_{C} f\left(C\right)\)，其中 \(C\) 是圆排列， \(f\left(C\right)\) 是断环的方式数，使得前缀和大于等于 \(0\)，也等价于找到一个合法的断环方式，此时 \(f\left(C\right)\) 就是使得部分和为 \(0\) 的位置数。

这不就是定义吗？显然一个环的多个贡献给我们的计数造成了麻烦。

考虑转换一下，使环的贡献只能是 \(1\)。

如果见过 \(\texttt{Raney}\) 引理，就会发现一个类似的地方：

下面摘自《具体数学》301页 原话：

如果 \(\left< x_1, x_2, \dots , x_m \right>\) 是任何一个其和为 \(+1\) 的整数序列，那么它的循环移位

\[\left< x_1, x_2, \dots , x_m \right>，\left< x_2, \dots ,x_m,x_1 \right>，\dots，\left< x_m, x_1,\dots ,x_{m-1} \right> \]

中恰好有一个满足所有的部分和都是正数。

可以感性理解一下

然后提供了一个例子，就是往卡特兰数计数时，序列最前面加一个 \(1\)。然后容易计数。

这道题的部分和非负，如果在序列前面加个 \(1\)，不就是 \(\texttt{Raney}\) 引理了？

我们考虑像这个引理一样，在序列头加一个 \(1\)，可以发现，并不是所有地方都能加，例如 \(2,-1,-1\)，如果在 \(2\) 后面加 \(1\) 显然是不行的。然后发现加的方案数正好和上面的 \(f\left( C\right)\) 一样——这不是加了跟没加一样？

但是不用担心，我们考虑黑科技，不加 \(1\)，改成加 \(-1\)。

我们往原序列里插入一个 \({-1}^*\) ，此时问题转换为对圆排列找出一种断环方式，使得前 \(m\) 个的部分和非负，并且元素和为 \(-1\)。

易证最后一个必定是 \(-1\)，并且用类似方法可以证明一定存在且仅存在一个满足条件的断环方式。（我不会证，逃

由于有标号，有 \(m – n + 1\) 个 \(-1\)，于是最后一个 \(-1\) 就有 \(m – n + 1\) 种标号。我们要钦定最后一个 \(-1\) 为 \({-1}^*\)，所以答案要除以 \(m – n + 1\)。

\(m + 1\) 个元素的圆排列方案数为 \(m!\)，于是答案就是 \(\frac{m!}{m – n + 1}\)。

复杂度 \(O\left(m\right)\)，可以通过此题。

使用快速阶乘可以得到更低的复杂度以及更大的常数。

#include <bits/stdc++.h>

const int mod = 998244353;
typedef long long LL;
int n, m;
int main() {
	std::cin >> n;
	for (int i = 1, t; i <= n; ++i) std::cin >> t, m += t;
	int ans = 1;
	for (int i = 2; i <= m; ++i)
		if (i != m - n + 1)
			ans = (LL) ans * i % mod;
	std::cout << ans << std::endl;
	return 0;
}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/167479.html原文链接：https://javaforall.cn