P11159 【MX-X6-T5】再生 题解

w9095

2024-10-03 22:51:53

题解

P11159 【MX-X6-T5】再生

简单数学题。

首先根不同肯定是在诈骗,最长的链的链顶就是树根。然后考虑一条长链内,除了链顶都可以随意排序,对于每条链,答案乘上链中元素数量减一的阶乘。

然后考虑把这些链提取出来,重新拼接成一棵树。注意到如果先拼短链再拼长链,长链会影响到短链,限制较多,而先拼长链再拼短链限制更容易满足,考虑先拼长链。

对于每一条拼过的链,为了满足其长链剖分性质,如果这条链的长度为 siz[i],则长度为 siz[j] 的新拼的链只能拼在较高的 siz[i]-siz[j] 个位置中,否则会破坏长链剖分性质。不难发现对于每一条拼过的链都有这个限制,而我们已经拼上去的链的总长度是已知的,拼过的链的数量也是已知的,所以减去的总量也是已知的,两者做差就是这条链的拼接方案数,乘法原理贡献到答案里即可。

#include <bits/stdc++.h>
using namespace std;
long long n,a[600000],c[600000],s[600000],jc[600000],siz[600000],ans=1,cnt=0;
const long long mod=20051131;
int main()
{
    scanf("%lld",&n);
    jc[0]=1;
    for(int i=1;i<=n;i++)jc[i]=jc[i-1]*i%mod,siz[i]=0;
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]),siz[a[i]]++;
    for(int i=1;i<=n;i++)
        {
            if(siz[i]==0)continue;
            c[++cnt]=siz[i],ans=ans*jc[siz[i]-1]%mod;
        }
    sort(c+1,c+cnt+1);
    for(int i=cnt;i>=1;i--)s[i]=s[i+1]+c[i];
    for(int i=1;i<=cnt-1;i++)ans=ans*(s[i]-(cnt-i+1)*c[i])%mod;
    printf("%lld\n",ans);
    return 0;
}