#P2109. [NOI2007] 生成树计数
[NOI2007] 生成树计数
题目描述
最近,小栋在无向连通图的生成树个数计算方面有了惊人的进展,他发现:
- 个结点的环的生成树个数为 。
- 个结点的完全图的生成树个数为 。
这两个发现让小栋欣喜若狂,由此更加坚定了他继续计算生成树个数的想法,他要计算出各种各样图的生成树数目。
一天,小栋和同学聚会,大家围坐在一张大圆桌周围。小栋看了看,马上想到了生成树问题。如果把每个同学看成一个结点,邻座(结点间距离为 )的同学间连一条边,就变成了一个环。可是,小栋对环的计数已经十分娴熟且不再感兴趣。于是,小栋又把图变了一下:不仅把邻座的同学之间连一条边,还把相隔一个座位(结点间距离为 )的同学之间也连一条边,将结点间有边直接相连的这两种情况统称为 有边相连,如图 所示。
小栋以前没有计算过这类图的生成树个数,但是,他想起了老师讲过的计算任意图的生成树个数的一种通用方法:构造一个 的矩阵 ,其中:
$$a_{i,j}=\begin{cases} d_i & i=j \\ -1 & \text{$i, j$ 之间有边直接相连} \\ 0 & \text{其他情况} \end{cases}$$与图 1 相应的 矩阵如下所示。为了计算图 1 所对应的生成数的个数,只要去掉矩阵 的最后一行和最后一列,得到一个 的矩阵 ,计算出矩阵 的行列式的值便可得到图 1 的生成树的个数。
$$A=\begin{bmatrix} 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{bmatrix},\\ B=\begin{bmatrix} 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{bmatrix}, $$所以生成树的个数为 。小栋发现利用通用方法,因计算过于复杂而很难算出来,而且用其他方法也难以找到更简便的公式进行计算。于是,他将图做了简化,从一个地方将圆桌断开,这样所有的同学形成了一条链,连接距离为 1 和距离为 2 的点。例如八个点的情形如下:
这样生成树的总数就减少了很多。小栋不停的思考,一直到聚会结束,终于找到了一种快捷的方法计算出这个图的生成树个数。可是,如果把距离为 的点也连起来,小栋就不知道如何快捷计算了。现在,请你帮助小栋计算这类图的生成树的数目。
输入格式
输入文件中包含两个整数 ,由一个空格分隔。 表示要将所有距离不超过 (含 )的结点连接起来, 表示有 个结点。
输出格式
输出文件输出一个整数,表示生成树的个数。由于答案可能比较大,所以你只要输出答案除 的余数即可。
3 5
75
提示
样例对应的图如下:
$$A = \begin{bmatrix} 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{bmatrix}, B = \begin{bmatrix} 3 & -1 & -1 & -1 \\ -1 & 4 & -1 & -1 \\ -1 & -1 & 4 & -1 \\ -1 & -1 & -1 & 4 \\ \end{bmatrix}, \det B = 75 $$数据规模和约定
此外,对于所有数据,。
提示
以下为行列式的一种计算方法。记 表示排列 中逆序对的数量,那么可以求得矩阵 的行列式如下:
$$\det B=\sum_{\bm P=[p_1,p_2,\cdots,p_n]} (-1)^{\sigma(\bm P)} \prod_{i=1}^n b_{i,p_i} $$例如,对于 $B=\begin{bmatrix}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 0\end{bmatrix}$,其行列式计算如下:
$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|}\hline \bm P & \sigma(\bm P) & b_{1,p_1} & b_{2,p_2} & b_{3,p_3} & (-1)^{\sigma(\bm P)}\prod_{i=1}^n b_{i,p_i} \\ \hline [1, 2, 3] & 0 & 1 & 5 & 0 & 0 \\ \hline [1, 3, 2] & 1 & 1 & 6 & 8 & -48 \\\hline [2, 1, 3] & 1 & 2 & 4 & 0 & 0 \\\hline [2, 3, 1] & 2 & 2 & 6 & 7 & 84 \\\hline [3, 1, 2] & 2 & 3 & 4 & 8 & 96 \\\hline [3, 2, 1] & 3 & 3 & 5 & 7 & -105 \\\hline \end{array} $$所以 的行列式值为 。