HackerRank Combinatorics – Circles Math

Challenge: Circles Math

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 100.0 / 100

Submission status: Accepted

Submission score: 1.0

Submission ID: 464803478

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/circles-math/problem

Cerinta

You are given a set A containing *n* integers from 1 to *n*; A = {1,2,3,...n}.  
Let's call P(A) as a set that contains all [permutations](http://en.wikipedia.org/wiki/Permutation) of A;  
For eg: if A = {1,2}. P(A) = {{1,2},{2,1}}

Can you find the number of elements *a* ∈ P(A) which satisfies following conditions:

+ For every 1 <= i <= n, a[i] ≠ i where a[i] is the i<sup>th</sup> integer in permutation a
+ There exists a set of *k* integers {i<sub>1</sub>, i<sub>2</sub>, i<sub>3</sub>, .... i<sub>k</sub>} such that 
a[i<sub>j</sub>] = i<sub>j+1</sub> ∀ j < k and a[i<sub>k</sub>] = i<sub>1 (cyclic)

**Input Format**  
The first line contains an integer T indicating the number of test-cases.
T lines follow. Each line has two integers n and k separated by a single space.

**Constraints**  
1 <= T <= 100  
1 <= k <= n <= 10<sup>6</sup>

**Output Format**  
Output the remainder of the answer after divided by 1000000007 ie., (10<sup>9</sup>+7)

**Sample Input**
 
    4
    3 2
    4 2
    5 3
    6 2

**Sample Output**

    0
    3
    20
    105

<strong>Hint</strong><br>
10<sup>9</sup>+7 is a <strong>prime number.</strong>

**Explanation**

*note* : Array's are 1 indexed. 

Lets take a look at N = 3 and K = 2

We will get 2 sets of A that satisfy the first property a[i] ≠ i, they are 

+ [3,1,2]
+ [2,3,1]

Now, as K = 2, we can have 6 such elements. 

+ [1,2], [1,3],[2,3], [2,1], [3,1], [3,2]

Lets consider the first element of P(A) -> [3,1,2] 

+ [1,2], a[1] ≠ 2
+ [1,3], a[1] = 3 but a[3] ≠ 1
+ [2,3], a[2] ≠ 3
+ [2,1], a[2] = 1 but a[1] ≠ 2
+ [3,1], a[3] = 1 but a[1] ≠ 3
+ [3,2], a[3] ≠ 2

Lets consider the second element of P(A) -> [2,3,1]

+ [1,2], a[1] = 2 but a[2] ≠ 1
+ [1,3], a[1] ≠ 3
+ [2,3], a[2] = 3 but a[3] ≠ 3
+ [2,1], a[2] ≠ 1
+ [3,1], a[3] = but a[1] ≠ 3
+ [3,2], a[3] ≠ 2

As none of the elements of a satisfy the properties above, hence 0. 

In the second case, n=4,k=2. Here follows all the permutations of 

A={1,2,3,4} we could find that satisfy the two condition above.

2 1 4 3 # (a[2] = 1, a[1] = 2) or (a[4] = 3, a[3] = 4) is ok.

4 3 2 1 # (a[4] = 1, a[1] = 4) or (a[3] = 2, a[2] = 3) is ok.

3 4 1 2 # (a[3] = 1, a[1] = 3) or (a[4] = 2, a[2] = 4) is ok.

**Timelimits**
Timelimits for this challenge is given [here](https://www.hackerrank.com/environment)

Cod sursa

#include <bits/stdc++.h>
using namespace std;

static const long long MOD = 1000000007LL;

static long long mod_pow(long long a, long long e) {
    long long r = 1 % MOD;
    a %= MOD;
    while (e > 0) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}
static long long inv(long long x){ return mod_pow(x, MOD-2); }

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;

    const int MAXN = 1000000;
    static long long fact[MAXN+1], invfact[MAXN+1], der[MAXN+1];

    fact[0] = 1;
    for (int i = 1; i <= MAXN; i++) fact[i] = fact[i-1] * i % MOD;
    invfact[MAXN] = inv(fact[MAXN]);
    for (int i = MAXN; i >= 1; i--) invfact[i-1] = invfact[i] * i % MOD;

    long long dm = 1;
    der[0] = 1;
    for (int i = 1; i <= MAXN; i++) {
        dm = (dm + ((i%2==0)? invfact[i] : (MOD - invfact[i]))) % MOD;
        der[i] = fact[i] * dm % MOD;
    }

    while(T--){
        int n,k; cin >> n >> k;
        if (k == 1) { cout << 0 << "\n"; continue; }

        long long invk = inv(k);

        long long res = 0;
        int maxCycles = n / k;
        long long invkPow = invk;

        for (int i = 1; i <= maxCycles; i++) {
            long long coef = fact[n] * invfact[n - i*k] % MOD;
            coef = coef * invkPow % MOD;
            coef = coef * invfact[i] % MOD;

            long long add = coef * der[n - i*k] % MOD;
            if (i % 2 == 1) res = (res + add) % MOD;
            else res = (res - add + MOD) % MOD;

            invkPow = invkPow * invk % MOD;
        }

        cout << res << "\n";
    }

    return 0;
}