网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
生成树计数
成绩 | 0 | 开启时间 | 2013年01月16日 星期三 10:40 |
折扣 | 0.8 | 折扣时间 | 2013年01月16日 星期三 10:40 |
允许迟交 | 是 | 关闭时间 | 2013年01月16日 星期三 10:40 |
输入文件 | scsjs.in | 输出文件 | scsjs.out |
【问题描述】
最近,小栋在无向连通图的生成树个数计算方面有了惊人的进展,他发现: ·n个结点的环的生成树个数为n。
·n个结点的完全图的生成树个数为n n-2。
这两个发现让小栋欣喜若狂,由此更加坚定了他继续计算生成树个数的想法,他要计算出各种各样图的生成树数目。
一天,小栋和同学聚会,大家围坐在一张大圆桌周围。小栋看了看,马上想到了生成树问题。如果把每个同学看成一个结点,邻座(结点间距离为1)的同学间连一 条边,就变成了一个环。可是,小栋对环的计数已经十分娴熟且不再感兴趣。于是,小栋又把图变了一下:不仅把邻座的同学之间连一条边,还把相隔一个座位(结 点间距离为2)的同学之间也连一条边,将结点间有边直接相连的这两种情况统称为有边相连,如图1所示。
小栋以前没有计算过这类图的生成树个数,但是,他想起了老师讲过的计算任意图的生成树个数的一种通用方法:构造一个n×n的矩阵A={aij}
其中di表示结点i的度数。
与图1相应的A矩阵如下所示。为了计算图1所对应的生成数的个数,只要去掉矩阵A的最后一行和最后一列,得到一个(n-1)×(n-1)的矩阵B,计算出矩阵B的行列式的值便可得到图1的生成树的个数。
所以生成树的个数为|B|=3528。小栋发现利用通用方法,因计算过于复杂而很难算出来,而且用其他方法也难以找到更简便的公式进行计算。于是,他将图做了简化,从一个地方将圆桌断开,这样所有的同学形成了一条链,连接距离为1和距离为2的点。例如八个点的情形如下:
这样生成树的总数就减少了很多。小栋不停的思考,一直到聚会结束,终于找到了一种快捷的方法计算出这个图的生成树个数。可是,如果把距离为3的点也连起来,小栋就不知道如何快捷计算了。现在,请你帮助小栋计算这类图的生成树的数目。
【输入格式】
输入文件中包含两个整数k, n,由一个空格分隔。k表示要将所有距离不超过k(含k)的结点连接起来,n表示有n个结点。
【输出格式】
输出文件输出一个整数,表示生成树的个数。由于答案可能比较大,所以你只要输出答案除65521的余数即可。
【输入样例】
3 5
【输出样例】
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^15 |
5 | k≤3 | n≤100 | 10 | k≤5 | n≤10^15 |
提示
行列式的一种计算方法,记α(P)表示P中逆序对的个数,令B的行列式
所以B的行列式为0-48+0+84+96-105=27。