再生
笑点解析：一开始乘法原理推错式子胡了个依赖链长种类数 \(\le \sqrt n\) 的做法上去。
有了 \(top\) 数组，显然可以求出每个点所处的长链。对于长链上的点，如果链长为 \(x\)，那么这条链有 \((x - 1)!\) 种可能的情况，因为链头是已经被确定了的。
考虑对形态计数。显然大的长链不能接到短的长链上。于是将链长从大到小排序，如果把长为 \(x\) 的链接到长度为 \(y\) 的链上，则有 \(y - x\) 种情况。对于当前添加的链，显然可以把这些情况直接相加，维护一个 \(\sum y - x\) 的式子，最后乘到总方案数里即可。
可以桶排序 + 前缀和维护，时间复杂度 \(O(n)\)。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi = pair<int, int>;
const int N = 500005;
const ll mod = 20051131;
int n, top[N], a[N];
ll ans = 1, f[N], tot[N];
int main()
{//freopen("sample.in", "r", stdin);//freopen("sample.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;f[0] = 1;for(int i = 1; i <= n; i++){cin >> top[i];a[top[i]]++;f[i] = (f[i - 1] * i) % mod;}for(int i = 1; i <= n; i++){if(a[i] == 0) continue;ans = (ans * f[a[i] - 1]) % mod;tot[a[i]]++;}ll suf = 0;for(int i = n, j = 0; i >= 1; i--){while(tot[i]--){if((suf - j * i) != 0) ans = (ans * (suf - j * i) % mod) % mod;suf += i;j++;}}cout << ans;return 0;
}