企业官网建设流程全解析

P11159 【MX-X6-T5】 再生

题目背景

原题链接：https://oier.team/problems/X6F。

このまま$\$
らったった$\$
音に乗って$\$
今きっと世界で僕だけだ$\$
後ろ向きな歌を聴いて$\$
少しだけ$\$
前向きに生きていく

—— 再生 - Nanatsukaze

破碎的点依照破碎的规则进行重组，如此再生的一个结构将会是什么样的呢？

题目描述

现有一棵n nn个点的有标号有根树，给定其长链剖分得到的 top 数组，请你输出有多少种不同的树可以在长链剖分之后得到该 top 数组。答案对20051131 2005113120051131（质数）取模。

具体来说，对于一棵树T TT，对所有点u uu定义其树高h u h_uhu​：

• 如果u uu是叶子，则h u = 1 h_u=1hu​=1。
• 否则设u uu的孩子集合为S u S_uSu​，则h u = max ⁡ v ∈ S u h v + 1 h_u=\max\limits_{v\in S_u}h_v + 1hu​=v∈Su​max​hv​+1。

给定数组t 1 ⋯ n t_{1\cdots n}t1⋯n​，你需要计算有多少种树满足：

• 对于根节点r rr，满足t r = r t_r=rtr​=r。
• 对于每一个不是叶子的节点u uu，存在恰好一个孩子v vv满足h v + 1 = h u h_v+1=h_uhv​+1=hu​并且t v = t u t_v=t_utv​=tu​，其他孩子满足t v = v t_v=vtv​=v。

模20051131 2005113120051131（质数）。

两棵树不同当且仅当它们的根不同或它们的边集不同。

保证答案不为0 \bf 00，但是不保证答案在模意义下不为0 \bf 00。

输入格式

第一行一个正整数n nn。

接下来一行，n nn个空格分隔的正整数t 1 ⋯ n t_{1\cdots n}t1⋯n​，表示 top 数组。

输出格式

一行一个整数表示答案对20051131 2005113120051131取模的值。

输入输出样例 #1

输入 #1

5 1 1 1 4 4

输出 #1

2

输入输出样例 #2

输入 #2

16 1 2 1 4 1 4 1 4 9 1 1 12 1 1 12 1

输出 #2

7181107

说明/提示

【样例解释 #1】

仅有图中的两种树满足条件。

【数据范围】

对于所有数据，保证1 ≤ n ≤ 5 × 10 5 1\leq n\leq 5\times 10^51≤n≤5×105，1 ≤ t i ≤ i 1\leq t_i\leq i1≤ti​≤i，保证取模前答案不为0 00。

捆绑测试，共 5 个 Subtask，具体限制如下所示：

• Subtask 1（11 pts）：t i = 1 t_i=1ti​=1。
• Subtask 2（24 pts）：n ≤ 5 n\leq 5n≤5。
• Subtask 3（17 pts）：n ≤ 16 n\leq 16n≤16。
• Subtask 4（22 pts）：n ≤ 2 × 10 3 n\leq 2\times 10^3n≤2×103。
• Subtask 5（26 pts）：无特殊限制。

C++实现

#include<bits/stdc++.h>#defineintlonglong#definelowbit(x)((x)&-(x))#definemod20051131#defineMAXN10000005usingnamespacestd;intn,k,t[MAXN],f[MAXN],ans;map<int,int>mp;vector<int>vec;voidupdate(intx){while(x<=n){t[x]++;x+=lowbit(x);}}intquery(intx){intans=0;while(x){ans+=t[x];x^=lowbit(x);}returnans;}signedmain(){f[0]=1;for(inti=1;i<=1000000;i++){f[i]=f[i-1]*i%mod;}cin>>n;for(inti=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(inti:vec){if(ans==0){ans=f[i-1];for(intj=1;j<=i;j++){update(j);}continue;}ans*=f[i-1];ans%=mod;ans*=query(n)-query(i);ans%=mod;for(intj=1;j<=i;j++){update(j);}}cout<<ans<<endl;return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容