Sphere Online Judge

SPOJ Problem Set (classical)

1722. Life, the Universe, and Everything II

Problem code: RP

This problem tests your mathematic knowledge and your programming ability very much. Your task is to calculate the number of different Minimum Spanning Trees (MSTs) of a special undirected unweighted graph. The graph has n nodes numbered from 1 to n, and there is an edge between node i (1<=i<=n) and node j (1<=j<=n) if and only if 0<|i-j|<=k.


Multiple test cases, the number of them(<=8) is given in the very first line.

Each test case contains one line with two space-separated numbers k(1<=k<=5) and n(1<=n<=1015).


For each test case you should output one line, the number of different MSTs of the corresponding graph modulo 65521.


3 5


Added by:[Trichromatic] XilinX
Time limit:0.162s-0.469s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Languages:All except: C99 strict ERL JS SCM chicken
Resource:Chinese National Olympiad in Informatics 2007,Day 2; Translated by Blue Mary

hide comments
2009-05-20 13:10:23 Benjamin Jones
@Paul Draper
Yes! Just count unique spawn trees.
A spawn tree is unique iif its prufer code is unique.
(hey i'm hinting you)
2009-04-28 10:17:00 Paul Draper
What trees are unique? Is 1-2-3 unique from 2-1-3?
2009-04-28 10:09:21 Paul Draper
How does a minimum spanning tree and a general tree differ in an unweighted graph?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.