自动搬运

查看原文

来自洛谷，原作者为

	Register_int 分道扬镳

搬运于2025-08-24 23:04:47，当前版本为作者最后更新于2024-10-03 16:15:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑每一条长链，若长度为 $n$，则链内排列的方案为 $(n-1)!$。

接下来将长链并成树。若长度为 $x$ 的长链并在长度为 $y$ 的上，那么必定有 $x<y$。接上去的位置恰好有 $y-x$ 个，方案数为 $y-x$。

显然合并过程互不影响，枚举短的计算并到任意一条长链上的方案数，乘起来即可。用前缀和优化可做到 $O(n)$。

#include <bits/stdc++.h> 

using namespace std;

typedef long long ll;

const int MAXN = 5e5 + 10;
const int mod = 20051131;

int n, cnt[MAXN]; ll ans = 1, sum;

int main() {
	scanf("%d", &n);
	for (int i = 1, x; i <= n; i++) scanf("%d", &x), cnt[x]++;
	sort(cnt + 1, cnt + n + 1, greater<int>());
	for (int i = 1; i <= n; i++) {
		if (!cnt[i]) break;
		for (int j = 1; j < cnt[i]; j++) ans = ans * j % mod;
		if (i > 1) ans = ans * (sum - (ll)(i - 1) * cnt[i]) % mod; sum += cnt[i];
	}
	printf("%lld", ans);
}