StrangeColoring
Cognizance - Insomnia · 2019-04-11 · by Vasyl[alphacom]
Problem Statement
M points are lying on a line and are colored with N different colors (numbered 1 to N) such that each point is coloured with exactly 1 color.
Two colorings c1 and c2 are considered âdifferentâ if and only if there exist a pair of points such that their color is same in c1 but different in c2 or they are different in c1 and same in c2. Otherwise they are considered âsimilarâ.
We define a set of different coloring as the set consisting of colorings of points such that no two elements in it are considered âsimilarâ.
What is the size of the largest set of different coloring mod 109 + 7.
Constraints
- 1 <= min(N, M) <= 106
- 1 <= max(N, M) <= 1018
2 2 Returns: 2
The different colorings possible are {1, 1}, {1, 2}, {2, 1} and {2, 2}. Among them {1, 1} and {2, 2} are similar and {1, 2} and {2, 1} are similar. So the largest set of different colorings is 2. For example, {{1, 1}, {1, 2}} contain no similar coloring.
10 15 Returns: 381367934
433786 372898436353436743 Returns: 352191334
46081666066812996 673079 Returns: 32046816
255274740500851546 817786 Returns: 867332592
Submissions are judged against all 20 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class StrangeColoring with a public method int count(long long n, long long m) · 20 test cases · 2 s / 256 MB per case