StairsColoring
SRM 449 · 2009-09-23 · by dzhulgakov
Problem Statement
A very rich sultan built an enormous luxurious two-story palace containing several staircases. According to an old tradition, each staircase must:
- contain exactly N steps
- have a right angle in its base
- be built using exactly N rectangular blocks of arbitrary size
Staircases can be built using many different arrangements of blocks. For example, there are 5 ways to build a staircase with 3 steps:
To ensure that his palace is really the most luxurious in the world, the sultan decided to build one staircase for each possible arrangement of blocks.
The sultan is now preparing for a staircase coloring festival. He wants to paint each of the staircases in the palace in one of K different colors. Multiple staircases can be painted the same color, and it is not necessary to use all K colors. Help the sultan by calculating the total number of different ways he can color his staircases. The answer can be large, so return the count modulo 1000000123.
Constraints
- N will be between 1 and 1000000000, inclusive.
- K will be between 1 and 1000000000, inclusive.
3 2 Returns: 32
As shown in the picture above, there are exactly 5 different ways to build a staircase with 3 steps. Each staircase can be painted in one of 2 different colors, for a total of 32 possible color combinations.
2 2 Returns: 4
1 1 Returns: 1
Here, there is only one staircase and one color to paint it.
4 5 Returns: 103514887
7 77 Returns: 747707397
Submissions are judged against all 65 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class StairsColoring with a public method int coloringCount(int N, int K) · 65 test cases · 2 s / 256 MB per case