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

Luogu P14254 分割(divide) 题解 [ 蓝 ] [ 分类讨论 ] [ 组合计数 ]

分割

Think twice, code once.

首先观察合法划分的性质:

  • 树的深度集合是一段连续的区间,即 \([dep_{root}, dep_\max]\)
  • 因为 \(S_1\) 的根节点深度最小(\(\min L \ge L_{S_1}\)),而区间之交为 \([\max L, \min R]\)。因此 \(\max L \le L_{S_1}\)。由此可得 \(\forall 2 \le i \le k + 1, L_{S_i} = L_{S_1}\)。即所有选择的点深度相同
  • 最后的限制条件为 \(\min R_{S_i} = R_{S_1}\),即至少存在一棵树的最大深度为 \(R_{S_1}\)

到这里基本就做完这题了,枚举树的层数,对每一层分别计数即可。这里着重讲解组合计数、分类讨论的解题过程。

首先我们需要明确列出需要计数的序列满足什么条件:

  1. \(b_1\) 至少要有一个与之同层、最大深度相等的节点一起与它被割掉。
  2. 最大深度小于 \(b_1\) 的节点一律不能被割掉。
  3. 至少有一个最大深度大于等于 \(b_1\) 的不被割掉。

发现这些条件并不是互相独立的,于是可以将相似的 1、3 两条进行合并

\(b_1\) 一起被割掉的点必须满足最大深度大于等于 \(b_1\),但不能全部选择,也不能不选与 \(\bm{b_1}\) 相等的点

接下来梳理计数流程:

  1. 若该层的节点数 \(\le k\),无解。
  2. 对该层节点的最大深度排序。
  3. 从小到大枚举最大深度,对于每一类最大深度依次考虑:
    3.1 如果该最大深度只有一个节点,则一定割不了。
    3.1 先求出选择此类节点为 \(b_1\),剩下随便选最大深度大于等于 \(b_1\) 的节点的方案数。
    3.3 然后依次将选择了全部节点、不选与 \(b_1\) 相等的点的情况容斥掉。

此时依然无法通过,对拍后发现有一种特殊情况,说明了上述的第 1 个计数条件其实是不完备的:

\(b_1\) 不一定要有与之同层、最大深度相等的节点一起与它被割掉,可以将这个节点划分到 \(1\) 所在的树里,并保证树里其他节点的深度都没它大。简而言之,就是要把最大深度等于 \(b_1\) 的同层节点全都不割,而最大深度大于 \(b_1\) 的同层节点全部割掉。

就此实现,可以通过大样例和所有数据。时间复杂度 \(O(n\log n)\)

赛时在此题死磕三个小时且最终没有调出来,说明做题时的思路还不够清晰,以后要把所有计数的细节全部写在纸上,包括计数的式子,对拍时拍出的细节问题。有必要时将一些分类讨论情况进行合并、重构。

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
using pi = pair<int, int>;
const int N = 1000005;
const ll mod = 998244353;
int n, k, dep[N], mxdep[N];
int h[N], idx;
struct Edge{int v, ne;
}e[2 * N];
void add(int u, int v)
{e[++idx] = {v, h[u]};h[u] = idx;
}
vector<int> tot[N];
ll ans, f[N], g[N], inv[N];
void init()
{inv[1] = 1;for(int i = 2; i < N; i++)inv[i] = (mod - mod / i) * inv[mod % i] % mod;f[0] = g[0] = 1;for(int i = 1; i < N; i++){f[i] = (f[i - 1] * i) % mod;g[i] = (g[i - 1] * inv[i]) % mod;}
}
ll C(int n, int m)
{return (f[n] * g[n - m] % mod * g[m] % mod);
}
ll A(int n, int m)
{return (f[n] * g[n - m] % mod);
}
void dfs(int u)
{mxdep[u] = dep[u];for(int i = h[u]; i ; i = e[i].ne){int v = e[i].v;dep[v] = dep[u] + 1;dfs(v);mxdep[u] = max(mxdep[u], mxdep[v]);}tot[dep[u]].push_back(mxdep[u]);
}
int main()
{// freopen("divide.in","r",stdin);// freopen("divide.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);init();cin >> n >> k;for(int i = 2; i <= n; i++){int p;cin >> p;add(p, i);}dep[1] = 1;dfs(1);for(int i = 2; i <= mxdep[1]; i++){if(tot[i].size() == 0) continue;sort(tot[i].begin(), tot[i].end());int pre = 0, cnt = 0, preval = tot[i][0];for(int j = 0; j <= tot[i].size(); j++){int itm;if(j == tot[i].size()) itm = -1;else itm = tot[i][j];if(itm == preval){cnt++;pre++;continue;}// 若某一种最大深度只出现一次,则一定无解if(cnt == 1){cnt = 1;pre++;preval = itm;continue;}int y = int(tot[i].size()) - pre;// 比 mxdep 大的全部割掉,等于 mxdep 的只割一个的方案if(k == 1 + y)ans = (ans + cnt * f[y] % mod) % mod;// 普遍情况,枚举 x 的值for(int x = 2; x <= cnt && x <= k; x++){if(k - x > y) continue;ll tmp = cnt * C(cnt - 1, x - 1) % mod * A(k - 1, x - 1) % mod * A(y, k - x) % mod;ans = (ans + tmp) % mod;}// 如果可能把大于等于 mxdep 的全部割掉,则需要把不合法的方案容斥掉if(k == cnt + y) ans = (ans - cnt * f[k - 1] % mod) % mod;cnt = 1;pre++;preval = itm;}}cout << (ans % mod + mod) % mod;return 0;
}
http://www.hskmm.com/?act=detail&tid=33965

相关文章:

  • 嵌入式第六周作业任务二--PWM呼吸灯
  • 2022 ICPC Shenyang
  • tryhackme-预安全-网络安全简介-进攻性安全简介-01
  • 20231326第五周预习报告
  • 复矩阵的奇异值分解(SVD)
  • idea与cursor的整合方案
  • Codeforces Round 496 (Div. 3) F. Berland and the Shortest Paths
  • 《程序员修炼之道:从小工到专家》第五章读后感
  • 元推理框架,有机AI是天使
  • PWN手的成长之路-18_铁人三项(第五赛区)_2018_rop
  • Dotnet通过Http2解决CVE-2025-55315高危漏洞
  • 日志|JAVAWEB|YApi|vue-cli|VUE-Element
  • 20232401 2025-2026-1 《网络与系统攻防技术》实验二实验报告
  • FFT学习小结
  • OI 笑传 #20
  • 幂等的双倍快乐,你值得拥有
  • 2025.10.18——1黄
  • 10.18总结
  • 10.17总结
  • 软考中级学习总结(2)
  • 2025年粉末冶金制品/零件厂家推荐排行榜,高精度耐磨粉末冶金零件,优质粉末冶金制品公司推荐!
  • Neo4j 图数据库搭建和 Springboot 访问
  • 2025粉末冶金制品优质厂家推荐:鸿瑞粉末冶金,专业定制品质卓越!
  • AI元人文理论框架体系研究:价值原语化的文明演进机制与治理范式转变——声明Ai研究
  • 20251018
  • [buuctf]bjdctf_2020_router
  • AtCoder Beginner Contest 428 ABCDE 题目解析
  • 稻草火把下的星辰:回忆我的90年代求学路
  • 10月18日日记
  • 第九章-实战篇-运维杰克