a197: NOI2007 Day2.2.生成树计数
Tags :
Accepted rate : 8人/9人 ( 89% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-11-01 03:18

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


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

 

 

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

 

    di    i=j

 

aij= -1  ij有边相连

 

    0     其它 

 

 

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

 

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

 

 

 

A=

 

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

   

B=

 

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 的点
也连起来,小栋就不知道如何快捷计算了。现在,请你帮助小栋计算这类图的生
成树的数目。

Input
输入文件中包含两个整数k, n,由一个空格分隔。k 表示要将所有距离不超
k(含k)的结点连接起来,n 表示有n 个结点。
Output
输出文件输出一个整数,表示生成树的个数。由于答案可能比较大,所以你
只要输出答案除65521 的余数即可。
Sample Input
3 5
Sample Output
75
測資資訊:
記憶體限制: 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
Hint :

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


 

A=

 

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 

B=

 

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 范围
1k=2n≤106k≤5n≤100
2k=3n=57k≤3n≤2000
3k=4n≤108k≤5n≤10000
4k=5n=109k≤3n1015
5k≤3n≤10010k≤5n1015

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

 

 

|B|=P=p1p2pn1n的排列(-1)a(P) Πj=1n bi,pi 

 

如,

B=

  1  2  3

  4  5  6

  7  8  0

则计算如下:

Pa(P)b1,p1b1,p1b1,p1(-1)a(P) Πj=1n bi,pi
1 2 301500
1 3 21168-48
2 1 312400
2 3 1226784
3 1 2234896
3 2 13357-105

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

感谢morris1028提供图片。

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

Tags:
出處:
NOI2007Day2第二题 [管理者:
liouzhou_101 (王启圣)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」