6601: BZOJ2601:[Jsoi2011]同分异构体计数

Memory Limit:128 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Antonio 最近对有机化学比较感兴趣,他想请你帮助他快速计算出某种烃类的同分异 构体的数目。  为了表述方便,我们作出如下定义:    环烷烃: 具有n 个碳原子的环烷烃可以表示成一张具有n 个顶点n 条边的无向连通 简单图(基环+外向树)。每个顶点的度数不超过 4。    M-环烷烃:至多有m 个顶点在环上的环烷烃。(注意环上至少有 3 个顶点,因为 任意两个顶点之间至多只能有1 条边)。   同构:假设结构A和结构B 均具有n 个碳原子,A和B 同构当且仅当能够对A和 B 中的每个碳原子都按照 1~n 编号,使得对于编号为 v1 和 v2 的两个碳原子,他 们在 A中存在边相连当且仅当他们在 B中存在边相连。(换言之,A和 B对应的图 同构)。  现在,给出n, m,Antonio 希望你帮助他统计有多少种互不同构的含有n 个碳原子的 m-环烷烃。由于这个数量可能很大,你只需要输出它对p 的余数。(p是一个素数)。  在本题中,我们不考虑某结构在化学上是否能够稳定存在,也不考虑其他的异构方式。


输入格式

输入文件只有一行,用空格隔开的三个整数n, m, p 。保证有m <=n,p为素数。


输出格式

输出文件有且仅有一行,表示具有n 个碳原子的互不同构的m-环烷烃的数量,对 p的 余数。


样例输入

10 10 66103

样例输出

476

提示

 3 <=N<=1000,3<=M<= 50 ,且m<= n ,10^4<=P<= 2*10^9 10 ,且 p 为素数 


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: