#2356. 「NOI2007」 生成树计数

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: luyanaa

题目描述

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

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

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

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

\begin{equation} a_{ij}= \begin{cases} d_i &i=j \\ -1 &(i,j)\in V \\ 0 &(i,j)\notin V & i \neq j \end{cases} \end{equation}

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

\textbf{A}=\begin{matrix} 4 & -1 & -1 & 0 & 0 & 0 & -1 & -1 \\ -1 & 4 & -1 & -1 & 0 & 0 & 0 & -1 \\ -1 & -1 & 4 & -1 & -1 & 0 & 0 & 0 \\ 0 & -1 & -1 & -4 & -1 & -1 & 0 & 0 \\ 0 & 0 & -1 & -1 & 4 & -1 & -1 & 0 \\ 0 & 0 & 0 & -1 & -1 & 4 & -1 & -1 \\ -1 & 0 & 0 & 0 & -1 & -1 & 4 & -1 \\ -1 & -1 & 0 & 0 & 0 & -1 & -1 & 4 \end{matrix} \quad \textbf{B}=\begin{matrix} 4 & -1 & -1 & 0 & 0 & 0 & -1 \\ -1 & 4 & -1 & -1 & 0 & 0 & 0 \\ -1 & -1 & -4 & -1 & -1 & 0 & 0 \\ 0 & -1 & -1 & 4 & -1 & -1 & 0 \\ 0 & 0 & -1 & -1 & -4 & -1 & -1 \\ 0 & 0 & 0 & -1 & -1 & -4 & -1 \\ -1 & 0 & 0 & 0 & -1 & -1 & -4\end{matrix}

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

3(2).png

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

输入格式

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

输出格式

输出一个整数,表示生成树的个数。由于答案可能比较大,所以你只要输出答案除 65521 的余数即可。

样例

样例输入

3 5

样例输出

75

样例说明

样例对应的图如下:

捕获.JPG

\textbf{A}= \begin{matrix} 3 & -1 & -1 & -1 & 0 \\ -1 & 4 & -1 & -1 & -1 \\ -1 & -1 & 4 & -1 & -1 \\ -1 & -1 & -1 & 4 & -1 \\ 0 & -1 & -1 & -1 & 3 \end{matrix} \quad \textbf{B}= \begin{matrix} 3 & -1 & -1 & -1 \\ -1 & 4 & -1 & -1 \\ -1 & -1 & 4 & -1 \\ -1 & -1 & -1 & 4 \end{matrix} \quad |B|=75

数据范围与提示

数据规模和约定

对于所有的数据, 2 \le k \le n

数据编号 k 范围 n 范围 数据编号 k 范围 n 范围
1 k=2 n \le 10 6 k\le 5 n \le 100
2 k=3 n=5 7 k\le 3 n \le 2000
3 k=4 n \le 10 8 k\le 5​ n \le 10000
4 k=5 n=10 9 k\le 3 n \le 10^{15}
5 k\le 3 n \le 100 10 k\le 5

提示

1494_5.jpg.gif