P11159 题解

Register_int · 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);
}