DerangementsStrikeBack
SRM 717 · 2017-05-20 · by Arterm
Problem Statement
You are given two
Let D[i] be the number of permutations of the set {1,2,...,n+i} such that the first i values are not fixed points of the permutation. Formally, we are interested in permutations p such that for each j between 1 and i, inclusive, we have p(j) != j.
Next, let B[i] = (D[i] / n!) modulo (10^9 + 7). Note that it can be shown that D[i] divided by n! is always an integer.
Compute and return the bitwise xor of the values B[i] for i between 1 and m, inclusive.
Notes
- Author's solution explicitly computes each of the values B[i]. Bitwise xor is only used to reduce the size of the output.
Constraints
- n will be between 0 and 1,000,000,000, inclusive.
- m will be between 1 and 100,000, inclusive.
0 3 Returns: 3
As we have n=0, we are counting derangements, i.e., permutations with no fixed points. We can easily see that D[1]=0, D[2]=1, and D[3]=2. As 0! = 1, we also have B[1]=0, B[2]=1, and B[3]=2. Thus, the correct return value is (0 xor 1 xor 2) = 3.
1 3 Returns: 9
3 3 Returns: 73
4 1 Returns: 4
70 39 Returns: 319676671
Submissions are judged against all 118 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DerangementsStrikeBack with a public method int count(int n, int m) · 118 test cases · 2 s / 256 MB per case