Problem Statement
Long long ago the people in Byteland were almost wild and had no cities.
But there was one place they all liked and called it the Central Place of the Universe (CPU).
People where coming to CPU from all parts of Byteland at least once per year.
As a result, the country soon contained exactly k roads.
The roads were pairwise disjoint, except for one endpoint: each of the roads started at the CPU.
Later, Bytelandians decided to build some cities. Of course, each city needs a name, so they first came up with some names: Byte City, Bit City, New Byte, 7Bit, Hard Drive, Medium Drive, and many others. Together, they came up with exactly n names for the cities. Therefore, they decided to build exactly n cities. The locations (but not names) of k + 1 of those cities are certain: one city has to contain the CPU, and k other cities will lie on the opposite ends of the k roads. Bytelandians do not want to build any more roads, therefore each of the remaining n − k − 1 cities has to be built on one of the roads. Sadly, this still leaves a lot of options.
The Council of Elders started to draw all possible maps of Byteland so they can choose the nicest one and build the cities accordingly. For a particular map, two cities A and B are considered neighbors if we can get from A to B along one of the roads, without passing through another city. Two maps are different if and only if there is a city such that the set of its neighbors on one map is not equal to the set of its neighbors on the other map.
You are given the integer n and k. Compute and return the number of different maps, modulo 1,000,000,007.
Later, Bytelandians decided to build some cities. Of course, each city needs a name, so they first came up with some names: Byte City, Bit City, New Byte, 7Bit, Hard Drive, Medium Drive, and many others. Together, they came up with exactly n names for the cities. Therefore, they decided to build exactly n cities. The locations (but not names) of k + 1 of those cities are certain: one city has to contain the CPU, and k other cities will lie on the opposite ends of the k roads. Bytelandians do not want to build any more roads, therefore each of the remaining n − k − 1 cities has to be built on one of the roads. Sadly, this still leaves a lot of options.
The Council of Elders started to draw all possible maps of Byteland so they can choose the nicest one and build the cities accordingly. For a particular map, two cities A and B are considered neighbors if we can get from A to B along one of the roads, without passing through another city. Two maps are different if and only if there is a city such that the set of its neighbors on one map is not equal to the set of its neighbors on the other map.
You are given the integer n and k. Compute and return the number of different maps, modulo 1,000,000,007.
Definition
- Class:
- Byteland
- Method:
- CountDifferentMaps
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int CountDifferentMaps(int n, int k)
- (be sure your method is public)
Constraints
- n will be between 2 and 2^20, inclusive.
- k will be between 1 and n − 1, inclusive.
Examples
5
4
Returns: 5
There are 5 ways how to choose the central city (the one that will contain the CPU). For each choice there is only one possible map.6
3
Returns: 720
There are 5 ways how to choose the central city. For each such choice we know that there has to be one road with two cities and two roads with one city. There are 6 ways how to choose the two separate cities, and for each of them there are two ways for the order of the remaining two cities on their road. This gives us a total of 5 × 6 × 2 = 60 possible maps.
Back to all problems