Ninja And The New Year Guests

Approach: We will recursively find all possible permutations and then check for each of them whether it is following the condition or not.

 

We will maintain a counter based on that and increment it when the current permutation satisfies the condition.

 

Algorithm :  

// It is a recursive function to get all the permutations of the current array 'arr'.

void getPermutations(arr, index, k, ans)

1. If 'index' >= 'arr.size()' :
   • Initialize the variable 'count' by 0.
   • Run a loop over array 'arr'
     • If 'arr[i] == i' then increment 'count' by 1.
   • If 'count' >= 'k' then increment 'ans'.
   • Call return.
2. Run a loop from 'index' to 'arr.size()'.
   • Swap 'arr[index]' and 'arr[i]'.
   • Call 'getPermutations(arr, index + 1, k, ans)'.
   • Swap 'arr[index]' and 'arr[i]' again.
      

int numberOfPermutations(n, k)

1. Initialize the variable 'mod' by 1e9 + 7 and 'ans' by 0.
2. Initialize an empty vector 'arr'.
3. Run a loop from 0 to 'n - 1' and push each index in 'arr'.
4. Call 'getPermutations(arr, 0, k, ans)'
5. Return 'ans % mod'

Approach: 

Let's first fix the positions in the array such that 'ARR[I] != I', Say there are 'M' such positions. (0 <= M <= 'N - K')

Let's count the number of permutations with fixed 'M' for that, and we need to choose the indices having the 'ARR[I] !=I'. We can easily find this using the simple combination formula 'NCM'. 
 

Then we need to construct a permutation for chosen indices such that for every chosen index, 'ARR[I] !=I'; This is nothing but the derangements, and we will find this using an exhaustive search.
 

We will do the casework for this problem to find the derangements according to the 'K' value.

Algorithm :  
 

// Driver function to get the modular addition.

int add(a, b)

1. Initialize the variable 'mod' by 1e9 + 7.
2. Return '((a % mod) + (b % mod)) % mod'.

// Driver function to get the modular multiplication.

int mul(a, b)

1. Initialize the variable 'mod' by 1e9 + 7.
2. Return '((a % mod) * (b % mod)) % mod'.

// Driver function to get the modular binary exponention.

int bin_pow(a, b)

1. Initialize the variable 'mod' by 1e9 + 7.
2. Update 'a' with 'a % mod'
3. Initialize the variable 'res' by 1.
4. Run a while loop till 'b' > 0.
   • If 'b & 1' is true then update 'res' with 'res * a % mod'.
   • Update 'a' with 'a * a % mod'.
   • Update 'b' with 'b >>= 1'.
5. Return 'res'.

// Driver function to get the modular division.

int reverse(x)

1. Initialize the variable 'mod' by 1e9 + 7.
2. Return 'bin_pow(x, mod - 2)'.
    

int numberOfPermutations(n, k)

1. Update 'k' with 'n - k'.
2. Initialize the variable 'ans' by 1.
3. If 'k == 1' then return 'ans'.
4. Add 'mul(mul(n, n - 1), reverse(2))' to the 'ans'
5. If 'k == 2' then return 'ans'.
6. Add 'mul(mul(n, mul(n - 1, n - 2)), reverse(3))' to the 'ans'.
7. If 'k == 3' then return 'ans'.
8. Initialize the variable 'u' by 'mul(n, mul(n - 1, mul(n - 2, n - 3)))'.
9. Add 'mul(u, reverse(8))' to 'ans'.
10. Add 'mul(u, reverse(4))' to 'ans'
11. Return 'ans'.