当前位置: 首页 > news >正文

解题报告-洛谷SCP2025T2 P14254 分割(divide)

洛谷SCP2025T2 P14254 分割(divide)

题目描述

你是洛咕咕王国的土地测绘官。洛咕咕王国并购了一块新的领土,这块新的领土正等待被分配。

这块领土可被认为是一棵有 \(n\) 个结点、结点编号为 \(1\)\(n\) 的树,根为编号 \(1\)。为了便于表述,我们把每个结点 \(i\) 在原树中的深度记作 \(d_i\),并规定根的深度为 \(1\)

你的王国有若干位诸侯希望购买土地,因此现在要从这棵树中选出 \(k\)两两不同的结点,并把它们的编号排成一个有序序列 \(b=(b_1,b_2,\dots,b_k)\)。这个序列必须满足两个条件:

第一,每个被选的结点都不是根,并且它们的深度是非降的,也就是对所有 \(1\le i<k\)\(1 < d_{b_i} \le d_{b_{i+1}}\)

第二,按照序列里每一个结点 \(b_i\)\(i=1,2,\cdots,k\)),把它们各自与父亲的连边断开。断开这些 \(k\) 条边后,原树会被分成 \(k+1\) 棵互不相交的连通子树。我们把这 \(k+1\) 棵子树依次编号。其中,第 \(1\) 棵到第 \(k\) 棵对应于根为 \(b_1,\dots,b_k\) 的那 \(k\) 棵子树,而第 \(k+1\) 棵子树则是剩下的、包含原来的树根 \(1\) 的那一棵(它的根仍记为 \(1\))。对于第 \(i\) 棵子树,把该子树中所有结点在原树中的深度值去重后组成一个集合,记为 \(S_i\)。要求这次分割满足等式:

\[S_1 = \bigcap_{i=2}^{k+1} S_i \]

换言之,第 \(1\) 棵子树中出现的所有深度恰好是“出现在所有其他子树中的深度”的交集。

我们把任意两个序列 \(b\) 视为不同的方案当且仅当它们作为序列不同(即结点相同但顺序不同视为不同方案)。你的任务是计算满足上述条件的序列 \(b\) 的个数,对 \(998244353\) 取模后输出结果。

输入格式

第一行包含两个正整数 \(n,k\),分别表示树的结点个数和需要选出的结点个数。

第二行包含 \(n-1\) 个正整数,第 \(i\) 个正整数表示结点 \((i+1)\) 的父结点的编号 \(p_i\)。根结点 \(1\) 没有父结点。

输出格式

输出一行一个整数,表示满足题目条件的序列 \(b\) 的个数,结果对 \(998244353\) 取模。

输入输出样例 #1

输入 #1

11 2
1 2 3 1 1 5 6 8 1 10

输出 #1

4

输入输出样例 #2

输入 #2

13 3
1 2 3 1 1 5 6 8 1 10 11 7

输出 #2

72

输入输出样例 #3

输入 #3

7 3
1 1 1 1 2 3

输出 #3

12

说明/提示

【样例解释 #1】

如图,合法的序列 \(b\) 一共有 \(4\) 个,分别是:

  • \(b_1 = 5, b_2 = 10\)
  • \(b_1 = 10, b_2 = 5\)
  • \(b_1 = 7, b_2 = 11\)
  • \(b_1 = 11, b_2 = 7\)

\(b_1 = 5, b_2 = 10\) 为例,\(d_5 = 2\)\(d_{10} = 2\),有 \(d_5 \le d_{10}\)。当我们切断结点 \(5\)\(10\) 与其父结点 \(1\) 的连边后,原树被分割成三棵子树。第一棵子树以 \(b_1=5\) 为根,包含结点 \(\{5, 7\}\);第二棵子树以 \(b_2=10\) 为根,包含结点 \(\{10, 11\}\);第三棵子树则是包含原树根 \(1\) 的剩余部分。

对于第一棵子树,其结点在原树中的深度为 \(\{2, 3\}\),因此 \(S_1 = \{2, 3\}\)。对于第二棵子树,其结点深度同样为 \(\{2, 3\}\),所以 \(S_2 = \{2, 3\}\)。对于包含根结点的第三棵子树,去重后的深度集合为 \(S_3 = \{1, 2, 3, 4\}\)。计算交集可得 \(S_2 \cap S_3 = \{2, 3\}\),与 \(S_1\) 相等。因此 \(b_1 = 5, b_2 = 10\) 是一个符合条件的序列。

【样例解释 #2】

一个符合条件的序列 \(b\)\(b_1 = 4, b_2 = 9, b_3 = 12\)

【样例 #4】

见选手目录下的 divide/divide4.individe/divide4.ans

这个样例满足测试点 \(8\) 的条件限制。

【样例 #5】

见选手目录下的 divide/divide5.individe/divide5.ans

这个样例满足测试点 \(13\) 的条件限制。

【样例 #6】

见选手目录下的 divide/divide6.individe/divide6.ans

这个样例满足测试点 \(21\sim 25\) 的条件限制。


【数据范围】

本题共 \(25\) 个测试点,每个测试点占 \(4\) 分,共 \(100\) 分。

测试点编号 \(n\le\) 特殊性质
\(1\sim 2\) \(12\)
\(3\sim 5\) \(10^2\)
\(6\sim 7\) \(2\times 10^3\)
\(8\) ^ A
\(9\sim 10\) \(2\times 10^5\) ^
\(11\sim 12\) \(10^6\) ^
\(13\) \(2\times 10^5\) B
\(14\sim 15\) \(10^6\) ^
\(16\sim 20\) \(2\times 10^5\)
\(21\sim 25\) \(10^6\)

特殊性质 A:\(k=2\)
特殊性质 B:树为一棵满 \(t\) 叉树,其中 \(t \in [3,n)\cap \Z\)

对于 \(100\%\) 的数据,保证 \(2\le k< n\le10^6\)\(1 \leq p_i < i\)。树保证连通。


解题报告

数学还是不行,比赛时推导的式子太复杂并且太难调了,最终只得了 \(40\text{pts}\)

有一个很明显的性质,就是所选的节点必须在原树中的同一深度

为什么?首先所选的节点的深度必须不降,同时可以发现,如果节点 \(b_i(i >1)\) 的深度 \(dep_{b_i}\)\(b_1\) 的深度 \(dep_{b_1}\) 大,那么 \(S_i\) 相比于 \(S_1\) 肯定不包含深度 \([dep_{b_1},dep_{b_i}+1]\),也就不可能是合法情况。所以 所选的节点必须在原树中的同一深度。

那么我们就先把原树上的节点按深度分类,并求出每个子树的最长链的长度(即子树的根节点的高度)。

显然,为了满足条件,所选的节点 \(b_1\) 肯定是高度最小的。

因此,对于每一种深度,我们取出每个节点的高度并从小到大排序后,统计每一种高度的数量并用组合数学计算。这是为了保证 \(b_1\) 高度最小。

设一共有 \(tot\) 种高度,当前处理到第 \(h\) 种高度,数量为 \(cnt\),设 \(sum_{[l,r]}\) 表示高度在区间 \([l,r]\) 的节点个数。

计算方案数时有以下几点:

  • 显然,只有 \(sum[h,tot] \geq K+1\) 时才能有合法方案,\(+1\) 是保证原树的剩下部分的高度同样大于等于 \(b_1\)
  • 从当前高度所属的节点种选一个选为 \(b_1\),共有 \(cnt \times A_{sum_{[h,tot]}}^{k-1}\) 种总方案(包括合法和不合法的)。
  • 注意,如果 \(sum_{[h+1,tot]} \geq k\),我们就需要扣除不合法的方案数 \(A_{sum_{[h+1,tot]}}^{k-1}\),这是由于必须要选一个与 \(b_1\) 同高度的 \(b_2\) 来限制之后的并集。

比赛的时候脑卡了没有想到可以容斥,就硬分类讨论,成功把程序调爆了(可恶啊,我的 \(100\) 分和珍贵的时间!!!)。

时间复杂度 \(O(n \log n)\),修改后的正确代码如下:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF=0x3f3f3f3f;
const int mod=998244353;
const int N=3001100;#define ckmax(x,y) ( x=max(x,y) )
#define ckmin(x,y) ( x=min(x,y) )inline int read()
{int f=1,x=0; char ch=getchar();while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }while(isdigit(ch))  { x=x*10+ch-'0';    ch=getchar(); }return f*x;
}vector<int> e[N];
vector<int> pos[N];
int n,m,K,p[N];
int NUM[N],tot;void dfs(int u,int dep)
{pos[dep].push_back(u);ckmax(m,p[u]=dep);for(int i=0;i<e[u].size();i++){int v=e[u][i]; dfs(v,dep+1);ckmax(p[u],p[v]);}
}inline int FastPow(int x,int k)
{int tot=1;x%=mod;while(k){if(k&1) tot=(tot*x)%mod;x=(x*x)%mod;k>>=1;}return tot;
}int fact[N],infact[N];
inline void GetFact()
{fact[0]=1;for(int i=1;i<N;i++)fact[i]=fact[i-1]*i%mod;infact[N-1]=FastPow(fact[N-1],mod-2);for(int i=N-2;i>=0;i--)infact[i]=infact[i+1]*(i+1)%mod;
}inline int C(int n,int m)
{ return fact[n]*infact[m]%mod*infact[n-m]%mod; }inline int A(int n,int m)
{ return fact[n]*infact[n-m]%mod; }signed main()
{// freopen("divide.in","r",stdin);// freopen("divide.out","w",stdout);// 洛谷还是搞一个要用 freopen 的测评方式吧。n=read();K=read(); GetFact();for(int i=2;i<=n;i++)e[read()].push_back(i);dfs(1,1);int ans=0;for(int i=2;i<=m;i++){tot=0;for(int j=0;j<pos[i].size();j++)NUM[++tot]=p[pos[i][j]];sort(NUM,NUM+tot+1);int l=1,r=0;while(l<=tot){while(r<tot && NUM[r+1]==NUM[l]) r++;int cnt=r-l+1,sum=tot-l+1,suc=tot-r;if(sum>=K+1){ans=(ans+cnt*A(sum-1,K-1))%mod;if(suc>=K) ans=(ans-cnt*A(suc,K-1)%mod+mod)%mod;}l=r+1;}}printf("%lld\n",ans%mod);return 0;
}

这里附上 \(40\text{pts}\) 的神秘赛事代码,以表警示:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF=0x3f3f3f3f;
const int mod=998244353;
const int N=3001100;#define ckmax(x,y) ( x=max(x,y) )
#define ckmin(x,y) ( x=min(x,y) )inline int read()
{int f=1,x=0; char ch=getchar();while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }while(isdigit(ch))  { x=x*10+ch-'0';    ch=getchar(); }return f*x;
}vector<int> e[N];
vector<int> pos[N];
int n,m,K,p[N];
int NUM[N],tot;
int cnt[N],top;void dfs(int u,int dep)
{pos[dep].push_back(u);ckmax(m,p[u]=dep);for(int i=0;i<e[u].size();i++){int v=e[u][i]; dfs(v,dep+1);ckmax(p[u],p[v]);}
}inline int FastPow(int x,int k)
{int tot=1;x%=mod;while(k){if(k&1) tot=(tot*x)%mod;x=(x*x)%mod;k>>=1;}return tot;
}int fact[N],infact[N];
inline void GetFact()
{fact[0]=1;for(int i=1;i<N;i++)fact[i]=fact[i-1]*i%mod;infact[N-1]=FastPow(fact[N-1],mod-2);for(int i=N-2;i>=0;i--)infact[i]=infact[i+1]*(i+1)%mod;
}inline int C(int n,int m)
{ return fact[n]*infact[m]%mod*infact[n-m]%mod; }inline int A(int n,int m)
{ return fact[n]*infact[n-m]%mod; }inline int calc1(int sum)
{int ans=0;for(int j=1;j<=top;j++){if(sum<K+1) break;for(int k=2;k<=min(K-1,cnt[j]) && top>1;k++)ans=(ans+k*C(cnt[j],k)%mod*C(sum-cnt[j],K-k)%mod*A(K-1,K-1)%mod)%mod;if(cnt[j]>=K) ans=(ans+A(cnt[j],K))%mod;sum-=cnt[j];}return ans;
}inline int calc2(int sum)
{int ans=0;for(int j=1;j<=top;j++){sum-=cnt[j];if(sum>K || cnt[j]<=K-sum) continue;ans=(ans+C(cnt[j],K-sum)%mod*(K-sum)%mod*A(K-1,K-1)%mod)%mod;}return ans;
}signed main()
{n=read();K=read(); GetFact();for(int i=2;i<=n;i++)e[read()].push_back(i);dfs(1,1);int ans=0;for(int i=2;i<=m;i++){top=0,tot=0;int sum=0;for(int j=0;j<pos[i].size();j++)NUM[++tot]=p[pos[i][j]];sort(NUM,NUM+tot+1);for(int j=1;j<=tot;j++){if(NUM[j]!=NUM[j-1])sum+=cnt[top++];cnt[top]++;}sum+=cnt[top];if(sum>K){if(top>1){ans=(ans+calc1(sum))%mod;ans=(ans+calc2(sum))%mod;}elseans=(ans+A(sum,K))%mod;}for(int j=1;j<=top;j++) cnt[j]=0;}printf("%lld\n",ans%mod);return 0;
}
http://www.hskmm.com/?act=detail&tid=34413

相关文章:

  • 深入解析:Spring Cloud Netflix Eureka:从微服务基础到高可用集群实战
  • 2025.10.19——1绿1蓝
  • 别看我只是一只羊
  • 10.19 —— (VP)2022icpc西安
  • 2025年储罐源头厂家推荐排行榜,钢衬塑/钢塑复合/化工/防腐/PE/盐酸/硫酸/聚丙烯/不锈钢/次氯酸钠储罐公司精选!
  • 26-wsl-nginx-chinese-encoding-fix
  • win10-减少广告的三个操作
  • java方法
  • 变量名越怪,JVM 越快?
  • 深入解析:CPU调度算法简记
  • 2025年TYPE-C母座厂家推荐排行榜,防水/板上/沉板/立插/立贴/侧插/立式/插座/接口/插头/5A大电流/高速/TID认证公司精选
  • 在AI技术唾手可得的时代,挖掘用户真实需求成为制胜关键——某知名系统工具需求探索
  • 2025年通风气楼/通风天窗厂家推荐排行榜,圆拱型/电动/一字型/钢结构/流线型/屋顶自然/三角型/排烟/采光/启闭式/薄型/成品/消防联动/工厂/屋面/开敞式/启闭式排烟/通风设备公司推荐!
  • 科技领域导师制度与因果分析方法解析
  • 比赛与好题记录(2025 9-10)
  • 全面详解 C++std::vector用法指南
  • Visual Studio Code 初步配置指南(Windows端)
  • 2025年UV光源厂家推荐排行榜,UV面光源,UV LED点光源,UV LED面光源,UV LED固化机公司精选
  • 课上积极回答加分
  • 022304105叶骋恺数据采集第一次作业
  • 智能预加载:基于用户行为和路由预测
  • 函数简单传入参数的汇编分析 - 指南
  • 数据类型转换以及内存溢出
  • 美股数据接口对接指南:快速获取指数实时行情
  • 25-deepin-linux-wsl-nginx-installation
  • 2025国际冷链运输推荐腾翼搏时,专业温控保障生物药品安全!
  • 鸿蒙设备开发-gpio控制
  • AI Agent和Agentic AI
  • http基础
  • Java基础语法与面向对象