bzoj 1494 NOI2007 生成树计数

缘起

08年 IOI 国家队论文 《矩阵乘法在信息学中的应用 · 浙江省杭州二中 俞华程》 中的第一个例子~ bzoj 1494 NOI2007 生成树计数

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
一张无向图G有N (N <= 10^15)个点，编号为i的点和j的点之间有边，当且仅当|i-j|<=k（2<=k<=5）。
给定N, k, 求G的生成树的个数。

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

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

【样例输入】
3 5

【样例输出】
75

【限制】
5s 64MB

【来源】
NOI 2007

首先说几个结论

  1. n个结点的环的生成树个数为n。
  2. n个结点的完全图的生成树个数为n^(n-2)。

计算任意图的生成树个数的一种通用方法：构造一个n×n的矩阵A={aij},其中

img.png)

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

但是很遗憾，计算任意图的生成树的上述通用算法依旧对本题较为复杂. 其实通用算法并没有利用到图的特殊性。一张图的一个生成树就是这张图的一个无环子图，并且使所有点都连通。考虑到k的范围比较小，每个点都只和附近的很少的点连边。