DerangementsDiv2
SRM 717 · 2017-05-20 · by Arterm
Problem Statement
You are given two
Let D be the number of permutations of the set {1,2,...,n+m} such that the first m values are not fixed points of the permutation. Formally, we are interested in permutations p such that for each j between 1 and m, inclusive, we have p(j) != j.
Compute and return D modulo 1,000,000,007.
Constraints
- n will be between 0 and 50, inclusive.
- m will be between 1 and 50, inclusive.
0 2 Returns: 1
Here we are looking for permutations of {1, 2} such that p(1) != 1 and p(2) != 2. There is only one such permutation: the permutation (2, 1). In other words, the permutation p such that p(1) = 2 and p(2) = 1.
2 1 Returns: 4
Here we are counting permutations of {1, 2, 3} such that p(1) != 1. There are four such permutations: (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1). Here, (a, b, c) denotes a permutation p for which p(1) = a, p(2) = b, and p(3) = c.
1 2 Returns: 3
This time we want permutations of {1, 2, 3} such that p(1) != 1 and p(2) != 2. The three such permutations are (2, 1, 3), (2, 3, 1), and (3, 1, 2).
2 2 Returns: 14
3 5 Returns: 21234
20 27 Returns: 88437461
Watch out for integer overflow.
Submissions are judged against all 123 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DerangementsDiv2 with a public method int count(int n, int m) · 123 test cases · 2 s / 256 MB per case