F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 5307. -- [Zjoi2018]树

5307: [Zjoi2018]树

Time Limit: 30 Sec  Memory Limit: 512 MB
Submit: 17  Solved: 10
[Submit][Status][Discuss]

Description

九条可怜是一个热爱出题的女孩子。
虽然出题本身是一件非常有趣的事情,但是要把题目给出成正式比赛,就不是那么有趣了:
造数据总是一件让人心力憔悴的事情。
在ZJOI2018Day1中,可怜出了一道和树相关的非常有趣的题,
她打算采用一种常用的方式随机生成一棵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

Input

第一行输入三个整数n,k,p,表示节点个数,树的个数以及模数。
10^8<=p<=10^9,且p是质数。
N<=2000
K<=10^9

Output

输出一行一个整数,表示答案对p取模后的值。
即如果答案的最简分数表示为a/b,输出a×b−1 mod p。

Sample Input

2 2 998244353
3 2 998244353
4 2 998244353
10 2 998244353
50 233 998244353

Sample Output

1
499122177
332748118
113919852
634280054
样例中有五组不同的数据,所以输入格式略有不同。
在实际的测试数据中,输入只有一行。在第一组数据中,能够生成的树是唯一的,
因此生成的两棵树必定相同。
在第二组数据中,能够生成的树只有两种,他们是不同构的。
因此生成的两棵树同构的概率为1,在模998244353意义下为499122177。
在第三组数据中,能够生成的树有6种,如下图所示。
其中第二、三、四棵(第一排中间三棵)是同构的,其余两两不同构。
因此生成的两棵树同构的概率为1,在模998244353意义下为332748118。

HINT

Source

[Submit][Status][Discuss]

HOME Back