JOIN
Get Time

   Problem Statement  

 Problem Statement for DerangementsStrikeBack

Problem Statement

    

You are given two ints: n and m.

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.

 

Definition

    
Class:DerangementsStrikeBack
Method:count
Parameters:int, int
Returns:int
Method signature:int count(int n, int m)
(be sure your method is public)
    
 

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.
 

Examples

0)
    
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)
    
1
3
Returns: 9
2)
    
3
3
Returns: 73
3)
    
4
1
Returns: 4
4)
    
70
39
Returns: 319676671

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 717 Round 1 - Division I, Level Two