#2349. 树

    ID: 2349 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>PROV赛事:contest37来源:qoj.ac数据:公开样例组合数学

树

树

题目描述

1 树 1.1 题目描述 九条可怜是一个热爱出题的女孩子。 虽然出题本身是一件非常有趣的事情,但是要把题目给出成正式比赛,就不是那么有趣了: 造数据总是一件让人心力憔悴的事情。 在ZJOI2018 Day 1 中,可怜出了一道和树相关的非常有趣的题,她打算采用一种常用的 方式随机生成一棵n 个节点的有根树: • 节点1 作为树的根。 • 对于i ∈[2, n],独立地从[1, i) 中等概率随机选取一个节点作为i 的父亲。 可怜不是很想考虑这样随机出来的数据能不能卡掉暴力,毕竟乱搞也是OI 比赛的一部分。 可怜比较在意的是题目的区分度,以及是不是所有可能的分数都出现了。因此,可怜希望任何 两个测试点的树是有区别的:这样就可能会有错误的程序能只通过其中一个点。 因此,可怜想要计算,通过上面的方法独立的随机生成k 棵n 个节点的有根树T1 至Tk, 他们两两同构的概率是多少。 两棵n 个节点的有根树T1 和T2 同构当且仅当存在长度为n 的排列p,满足p1 = 1,且 对于∀i ∈[2, n],若i 在T1 的父亲是f,则pi 在T2 的父亲是pf。 1.2 输入格式 第一行输入三个整数n, k, p,表示节点个数,树的个数以及模数。输入保证108 ≤p ≤109 且p 是质数。 1.3 输出格式 输出一行一个整数,表示答案对p 取模后的值。即如果答案的最简分数表示为a b,输出 a × b−1 mod p。 1.4 样例输入 2 2 998244353 3 2 998244353 4 2 998244353 10 2 998244353 50 233 998244353 2

1.5 样例输出 1 499122177 332748118 113919852 634280054 1.6 样例解䞞 样例中有五组不同的数据,所以输入格式略有不同。在实际的测试数据中,输入只有一行。 在第一组数据中,能够生成的树是唯一的,因此生成的两棵树必定相同。 在第二组数据中,能够生成的树只有两种,他们是不同构的。因此生成的两棵树同构的概 率为1 2,在模998244353 意义下为499122177。 在第三组数据中,能够生成的树有6 种,如下图所示。其中第二、三、四棵(第一排中间 三棵)是同构的,其余两两不同构。因此生成的两棵树同构的概率为1 3,在模998244353 意义 下为332748118。 1.7 数据㣗围与约定 测试点 n k 测试点 n k 1 ≤5 =2 6 ≤50 ≤109 2 ≤10 7 ≤200 3 ≤20 8 ≤500 4 ≤50 9 ≤1000 5 10 ≤2000 对于100% 的数据,保证p 是质数且108 ≤p ≤109。 3

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2 2 998244353
1

样例 2

3 2 998244353
499122177