1363: #2356. 「NOI2007」 生成树计数

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

最近,小栋在无向连通图的生成树个数计算方面有了惊人的进展,他发现:

  • nnn 个结点的环的生成树个数为 nnn
  • nnn 个结点的完全图的生成树个数为 nn−2n^{n-2}nn2

这两个发现让小栋欣喜若狂,由此更加坚定了他继续计算生成树个数的想法,他要计算出各种各样图的生成树数目。
一天,小栋和同学聚会,大家围坐在一张大圆桌周围。小栋看了看,马上想到了生成树问题。如果把每个同学看成一个结点,邻座(结点间距离为 111 )的同 学间连一条边,就变成了一个环。可是,小栋对环的计数已经十分娴熟且不再感兴趣。于是,小栋又把图变了一下:不仅把邻座的同学之间连一条边,还把相隔 一个座位(结点间距离为 222 )的同学之间也连一条边,将结点间有边直接相连的这两种情况统称为有边相连,如 图 1 所示。

小栋以前没有计算过这类图的生成树个数,但是,他想起了老师讲过的计算任意图的生成树个数的一种通用方法:
构造一个 n×nn \times nn×n 的矩阵 A={aij}A=\{a_{ij}\}A={aij} ,其中:

aij=dii=j1(i,j)V0(i,j)Vij

其中 did_idi 表示结点 iii 的度数。与 图 1 相应的 AAA 矩阵如下所示。为了计算 图 1 所对应的生成数的个数,只要去掉矩阵 AAA 的最后一行和最后一列,得到一个(n−1)×(n−1)(n-1) \times (n-1)(n1)×(n1) 的矩阵 BBB ,计算出矩阵 BBB 的行列式的值,便可得到 图 1 的生成树的个数。

A=4110001114110001114110000114110000114110000114111000114111000114B=4110001141100011411000114110001141100011411000114

所以生成树的个数为 ∣B∣=3528|B|=3528B=3528 。小栋发现利用通用方法,因计算过于复杂而很难算出来,而且用其他方法也难以找到更简便的公式进行计算。于是,他将图做了简化,从一个地方将圆桌断开,这样所有的同学形成了一条链,连接距离为 111 和距离为 222 的点。例如八个点的情形如下:

3(2).png

这样生成树的总数就减少了很多。小栋不停的思考,一直到聚会结束,终于找到了一种快捷的方法计算出这个图的生成树个数。可是,如果把距离为 333 的点也连起来,小栋就不知道如何快捷计算了。现在,请你帮助小栋计算这类图的生成树的数目。

输入格式

输入中包含两个整数 k,nk , nk,n ,由一个空格分隔。 kkk 表示要将所有距离不超过 kkk (含 kkk )的结点连接起来, SubmitSubmit RecordStatisticsShowOff!