加成原理

· · 题解

很简单的一个题，为啥要放后面？

首先，显然，答案只跟每一种长度的链有多少个有关。

最长的链是从根开始的，因此最长的链只有一个，我们特判掉。

对于一个长度为 len 的链，除了头，其它的元素都是等价的，因此必然会对答案贡献 (len-1)! 的乘贡献（我们提前维护阶乘）。

从次长链向短链依次枚举，对于一个新来的链，看到底能放在多少个节点下，容易发现，只有下面的链长大于等于新来的链长的才能插入这个新链，想要维护这个，因为点数有限，就可以瞎搞了，我喜欢树状数组，因此下面的代码中使用树状数组。然后我们就做完了。

代码：

#include <bits/stdc++.h>
#define int long long
#define lowbit(x) ((x)&-(x))
#define mod 20051131
#define MAXN 10000005
using namespace std;
int n, k, t[MAXN], f[MAXN], ans;
map<int, int> mp;
vector<int> vec;
void update(int x) {
    while (x <= n) {
        t[x]++;
        x += lowbit(x);
    }
}
int query(int x) {
    int ans = 0;
    while (x) {
        ans += t[x];
        x ^= lowbit(x);
    }
    return ans;
}
signed main() {
    f[0] = 1;
    for (int i = 1; i <= 1000000; i++) {
        f[i] = f[i - 1] * i % mod;
    }
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> k;
        mp[k]++;
    }
    for (pair<int, int> i : mp) {
        vec.push_back(i.second);
    }
    sort(vec.begin(), vec.end());
    reverse(vec.begin(), vec.end());
    for (int i : vec) {
        if (ans == 0) {
            ans = f[i - 1];
            for (int j = 1; j <= i; j++) {
                update(j);
            }
            continue;
        }
        ans *= f[i - 1];
        ans %= mod;
        ans *= query(n) - query(i);
        ans %= mod;
        for (int j = 1; j <= i; j++) {
            update(j);
        }
    }
    cout << ans << endl;
    return 0;
}