标签 - matrix-tree

? solution ? ? matrix-tree ?    2017-03-22 19:34:22    859    0    1

题目描述

俗话说,跳蚤国王下江南,火车司机出秦川,共价大爷游长沙。
但是这道题可能跟上面几句话没什么关系。 共价爷想构造一棵 N 个点的有根树,其中 1 号点是根。
显然的,对于一棵有根树,我们可以定义每个点的深度为,这个点到根的路径上点的个数(包括端点),也就是说, 1 号点深度为 1
共价爷希望,深度为奇数的点的个数,刚好为 K 个。
他想知道有多少棵不同的满足条件的有根树,你只需要输出答案对 P 取模的结果。

我们认为两棵树不同,当且仅当存在一对点 (i,j) ,满足 ij 在一棵树中有边相连,而在另一棵树中没有边相连。

输入格式

一行三个整数,依次为 NK