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

· · 题解

P11159 排列组合题

赛时看到长链剖分吓一跳，因为我不会薯片剖分，然后仔细一看其实不难。

首先推一推发现：如果有一些点的 t_i 相同，那么它们就在一条链上。带着这条性质，我们开始写题。

Sub 1

所有的 t_i = 1，说明所有点都在一条链上，并且这条链的链头为 1，其他 n-1 个点在链上任意排列，答案即为 (n-1)!。

别忘了开 long long，即可通过此部分。

Sub 2 ~ 3

似乎可以用一种比较优雅的方式枚举出所有的树的形态，然后再行判断？蒟蒻赛时没有仔细考虑。

Sub 4

我们先按 t_i 不同分成若干组，也就是若干条链，我们要考虑如何将这些链拼接起来，再乘上链内部点的排列，即为答案。

为了保证长链剖分的性质，请看下图：

那么显然只能短链拼在长链上，我们先把链按照长度降序排序。

如果长链长度为 h_1，短链长度为 h_2，显然短链可以接在长链上方的 h_1-h_2 个节点上。

然后再枚举每条短链接在哪条长链上，答案累加起来，注意区分乘法原理和加法原理，我们可以得到以下代码：

（其中 fac[i] 表示阶乘。）

for(int i = 1;i <= n;i++)
{
    int fa = top[i];
    a[fa].h++;
}
sort(a+1,a+1+n,cmp);
ans = fac[a[1].h-1];
for(int i = 2;a[i].h;i++)
{
    a[i].v = fac[a[i].h-1];
    int cnt = 0;
    for(int j = 1;j < i;j++)
    {
        cnt += a[j].h-a[i].h;
    }
    ans = ans * cnt % mod * a[i].v % mod;
}
printf("%lld\n",ans);

时间复杂度 O(n^2)，即可通过此部分。

Sub 5

由代码得，每条链的 cnt（即这条链可以接在多少个点上）可以写作：

cnt_i = \sum\limits_{j = 1}^{i-1}h_j-h_i

这不是赤裸裸的前缀和嘛，于是就过了。

（其实不写结构体也行，赛时脑抽。）

#include<bits/stdc++.h>
#define N 500005
#define int long long
using namespace std;

const int mod = 20051131;
int n,top[N],ans;
struct node
{
    int id,h,v;
}a[N];
bool cmp(node x,node y)
{
    return x.h > y.h;
}

int fac[N];
void init()
{
    fac[0] = 1;
    for(int i = 1;i <= n;i++)fac[i] = fac[i-1] * i % mod; 
}

signed main()
{
    scanf("%lld",&n);
    for(int i = 1;i <= n;i++)
    {
        scanf("%lld",&top[i]);
    }
    init();
    for(int i = 1;i <= n;i++)
    {
        int fa = top[i];
        a[fa].h++;
    }
    sort(a+1,a+1+n,cmp);
    ans = fac[a[1].h-1];
    int sum = a[1].h;
    for(int i = 2;a[i].h;i++)
    {
        a[i].v = fac[a[i].h-1];
        int cnt = sum-(i-1)*a[i].h%mod;
        ans = ans * cnt % mod * a[i].v % mod;
        sum += a[i].h;
    }
    printf("%lld\n",ans);
    return 0;
}

感谢阅读！