a197. NOI2007 Day2.2.生成树计数 - 高中生程式解題系統

內容

最近，小栋在无向连通图的生成树个数计算方面有了惊人的进展，他发现：
·n 个结点的环的生成树个数为n。
·n 个结点的完全图的生成树个数为n^(n-2)。
这两个发现让小栋欣喜若狂，由此更加坚定了他继续计算生成树个数的想
法，他要计算出各种各样图的生成树数目。

一天，小栋和同学聚会，大家围坐在一张大圆桌周围。小栋看了看，马上想
到了生成树问题。如果把每个同学看成一个结点，邻座（结点间距离为1）的同
学间连一条边，就变成了一个环。可是，小栋对环的计数已经十分娴熟且不再感
兴趣。于是，小栋又把图变了一下：不仅把邻座的同学之间连一条边，还把相隔
一个座位（结点间距离为2）的同学之间也连一条边，将结点间有边直接相连的
这两种情况统称为有边相连，如图1 所示。

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

d_i i=j

a_ij= -1 i与j有边相连

0 其它

其中di 表示结点i 的度数。

与图1 相应的A 矩阵如下所示。为了计算图1 所对应的生成数的个数，只要
去掉矩阵A 的最后一行和最后一列，得到一个(n-1)×(n-1)的矩阵B，计算出矩阵
B 的行列式的值便可得到图1 的生成树的个数。

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

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

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

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

輸入說明

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

輸出說明

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

範例輸入 #1

3 5

範例輸出 #1

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (10%): 1.0s , <1K
公開測資點#1 (10%): 1.0s , <1K
公開測資點#2 (10%): 1.0s , <1K
公開測資點#3 (10%): 1.0s , <1K
公開測資點#4 (10%): 1.0s , <1K
公開測資點#5 (10%): 1.0s , <1K
公開測資點#6 (10%): 1.0s , <1K
公開測資點#7 (10%): 1.0s , <1K
公開測資點#8 (10%): 1.0s , <1K
公開測資點#9 (10%): 1.0s , <1K

提示：

【样例说明】样例对应的图如下：

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

3 -1 -1 -1

-1 4 -1 -1

-1 -1 4 -1

-1 -1 -1 4

|B| = 75

【数据规模和约定】

对于所有的数据2≤ k≤ n

数据编号	k 范围	n 范围	数据编号	k 范围	n 范围
1	k=2	n≤10	6	k≤5	n≤100
2	k=3	n=5	7	k≤3	n≤2000
3	k=4	n≤10	8	k≤5	n≤10000
4	k=5	n=10	9	k≤3	n≤10¹⁵
5	k≤3	n≤100	10	k≤5	n≤10¹⁵

【提示】行列式的一种计算方法，记α(P)表示P 中逆序对的个数，令B 的行列式

|B|=∑P=p₁p₂…p_n是1到n的排列(-1)^a(P) Π_j=1ⁿ bi,p_i

如，

1 2 3

4 5 6

7 8 0

则计算如下：

P	a(P)	b1,p₁	b1,p₁	b1,p₁	(-1)^a(P) Π_j=1ⁿ bi,p_i
1 2 3	0	1	5	0	0
1 3 2	1	1	6	8	-48
2 1 3	1	2	4	0	0
2 3 1	2	2	6	7	84
3 1 2	2	3	4	8	96
3 2 1	3	3	5	7	-105

所以B 的行列式为0-48+0+84+96-105=27。

感谢morris1028提供图片。

有些未删掉的多余信息，是为了让看不到图的人也能做。

標籤:

出處:

NOI 2007 Day2 第二题 [管理者： liouzhou_101 (王启圣) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」