PEG Judge - NOI '07 - Counting Spanning Trees

National Olympiad in Informatics, China, 2007

Day 2, Problem 2 - Counting Spanning Trees

Recently, Alex has made shocking advances in the technique of counting spanning trees in undirected, connected graphs. He discovered:

A cycle with n nodes contains n distinct spanning trees.
A complete graph with n nodes contains nⁿ⁻² distinct spanning trees.

These two discoveries have made Alex ecstatic, so he would like to continue on his adventure of counting spanning trees. That is, he would like to be able to count the number of spanning trees in all kinds of different graphs.

One day, Alex is meeting up with his peers. Everyone sat in a circle around a big round table. After taking a look, Alex immediately recalls his spanning tree problem. If he considers each of his peers as a node and neighboring peers (nodes with a distance of 1 between them) to be connected by an edge, then this becomes a cycle. However, Alex has already mastered calculations on cycles and is not really interested anymore. So, he changed the graph up a bit: Not only does he add an edge between neighboring peers, but he also adds an edge between pairs of peers who are separated by a single seat (nodes with a distance of 2 between them). Now, he considers peers connected by a single edge to be adjacent, as depicted in the following figure.

Alex has never tried counting spanning trees on this kind of graph before, however, he recalls his teacher explaining that there is a general method for counting the number of spanning trees on any type of graph. First, construct an n×n matrix A = { a_i j } such that:

$a_{ij} = \left\{\begin{matrix} d_i & i=j \\ -1 & i \textup{ and } j \textup{ are adjacent}\\ 0 & \textup{otherwise} \end{matrix}\right.$

where d_i represents the degree of node i.

Let's construct the matrix A corresponding to the graph of the round table as depicted above. To count the number of spanning trees, we only have to remove the last row and column of A, obtaining an (n−1)×(n−1) matrix which we shall call B. Computing the determinant of matrix B will yield the number of spanning trees in the graph above.

$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}$

Therefore the number of spanning trees in this graph is |B| = 3528. Alex noticed that using the general method, calculations are very complex and tedious. Yet, he cannot find any other formulas that are simpler than this. So, he simplified the graph. At some place he broke apart the circle around the table. This way, his peers form a chain of nodes, where an edge exist between all pairs of nodes with a distance of 1 or a distance of 2 of between them. The case for 8 nodes is depicted below:

This way, the total number of spanning trees is reduced by a great amount. Alex just thinks and thinks, until the entire meeting is over. Finally, he comes up with an efficient method to count the number of spanning trees in this graph. However, if he also decides to join nodes with a distance of 3, then once again he will not know how to find the answer efficiently. Please help Alex count the number of spanning trees in these types of graphs!

Input Format

The input contains two integers k and n, separated by a space. k means that all nodes with a distance no greater than k are to be linked by an edge in the graph. n indicates that there are n total nodes.

Output Format

Output a single integer, the number of spanning trees in the graph. Since the answer can be rather large, you are required to output the answer modulo 65521.

Sample Input

3 5

Sample Output

Explanation

The graph for the sample is depicted below:

$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}$ $\displaystyle |B| = 75$

Constraints

For all the test cases, 2 ≤ k ≤ n.

Test Case	Range of `k`	Range of `n`	Test Case	Range of `k`	Range of `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¹⁵

Hints

One method to compute the determinant is to first let α(P) represent the number of inversions in the sequence P. Then, the determinant of B is calculated using the formula:

$\displaystyle |B| = \sum_{P=p_1p_2...p_n\textup{ is a permutation of 1 to }n}(-1)^{\alpha(P)}\prod_{j=1}^n b_{i,p_i}$

If $\textstyle B = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 0 \\ \end{bmatrix}$ , then the calculations are as follows:

$\displaystyle P$	$\displaystyle \alpha(P)$	$\displaystyle b_{1,p_1}$	$\displaystyle b_{2,p_2}$	$\displaystyle b_{3,p_3}$	$\displaystyle (-1)^{\alpha(P)}\prod_{j=1}^n b_{i,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

Therefore the determinant of B is 0 − 48 + 0 + 84 + 96 − 105 = 27.

All Submissions
Best Solutions

Point Value: 30 (partial)
Time Limit: 1.00s
Memory Limit: 256M
Added: Jul 27, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...