HackerRank Algebra – Permutation Equations – ASOCIATIA „INVESTESTE PENTRU VIITORUL TAU” BUZAU

Challenge: Permutation Equations

Subdomeniu: Algebra (algebra)

Scor cont: 120.0 / 120

Submission status: Accepted

Submission score: 1.0

Submission ID: 464815717

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/permutation-equations/problem

Cerinta

Let *N* be a positive integer. Let's define a mapping *f* on the set
of permutations of integers from *1* to *N*, inclusive.
 Let *x = (x[1], ..., x[N])* be a permutation of integers from *1*
to *N*, inclusive.
 We define the permutation *y = (y[1], ..., y[N])* as follows.

-   *y[1] = 1*.
-   For *i \> 1* we consider number *z = x[y[i-1]]*.
    -   If *z* does not equal any of the numbers *y[1], ...,
        y[i-1]* then we set *y[i] = z*.
    -   Otherwise *y[i]* is defined as the smallest integer from *1*
        to *N* (inclusive) that does not equal any of the numbers
        *y[1], ..., y[i-1]*.

We consider permutation *y* as an image of *x* when mapping *f* is
applied to *x*. That is, we set *f(x) = y*.

Denote by *g(y)* the number of solutions of the equation *f(x) = y*.
That is, *g(y)* is the number of permutations *x* of integers from
*1* to *N*, inclusive, such that *f(x) = y*. 

**Challenge**  
For the given non-negative integers *L* and *R*, find the number of
permutations *y* of integers from *1* to *N*, inclusive, such that
*L ≤ g(y) ≤ R*. Since this number can be quite large output it modulo (*10<sup>9</sup> + 7*).

**Input Format**  
The first line contains an integer *T* denoting the
number of test cases. *T* test cases follow.  
Each test case consists of one line which contains three space-separated integers *N, L* and *R*.

**Output Format**  
For each test case, output a single line containing P *mod* (10<sup>9</sup>+7), where P is the required number of permutations.

**Constraints**

1 ≤ T ≤ 1000  
1 ≤ N ≤ 200,000  
0 ≤ L, R ≤ 10<sup>18</sup>


**Sample Input**  

    4  
    2 0 0  
    3 2 2  
    3 0 10  
    10 2 1  

**Sample Output**  

    1  
    1  
    6  
    0  

**Explanation**

**Example case 1.** The only permutation *y* for which equation *f(x)
= y* has no solutions is *y = (2, 1)*.

**Example case 2.** The only permutation *y* for which equation *f(x)
= y* has *2* solutions is *y = (1, 3, 2)*.
 The solutions are *x = (3, 2, 1)* and *x = (3, 1, 2)*.

**Example case 3.** For all *6* permutations *y* of numbers *{1, 2,
3}* we have *0 ≤ g(y) ≤ 10*.

**Example case 4.** Be careful, *L* could be greater than *R*. In
this case the answer is zero.

Cod sursa

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

static const int MOD = 1000000007;
static const int KMAX = 60; // because R <= 1e18

static inline int addm(int a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
    return a;
}

static inline int mulm(long long a, long long b) {
    return (int)((a * b) % MOD);
}

static int ceil_log2_pos(long long x) {
    // x >= 1
    int t = 0;
    long long v = 1;
    while (v < x && t < 62) {
        v <<= 1;
        ++t;
    }
    return t;
}

static int floor_log2_pos(long long x) {
    if (x <= 0) return -1;
    int t = 0;
    while ((t + 1) < 62 && (1LL << (t + 1)) <= x) ++t;
    return t;
}

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

    int T;
    cin >> T;
    vector<tuple<int,long long,long long>> qs(T);
    int nMax = 0;
    for (int i = 0; i < T; ++i) {
        int N;
        long long L, R;
        cin >> N >> L >> R;
        qs[i] = {N, L, R};
        nMax = max(nMax, N);
    }

    // factorials
    vector<int> fact(nMax + 1, 1);
    for (int i = 1; i <= nMax; ++i) fact[i] = mulm(fact[i - 1], i);

    // unsigned Stirling numbers of first kind: s(n,k), n up to nMax-1, k up to 60.
    vector<array<int, KMAX + 1>> stir(nMax);
    for (int k = 0; k <= KMAX; ++k) stir[0][k] = 0;
    stir[0][0] = 1;
    for (int n = 1; n <= nMax - 1; ++n) {
        stir[n][0] = 0;
        int mul = n - 1;
        for (int k = 1; k <= KMAX; ++k) {
            int v = stir[n - 1][k - 1];
            v = addm(v, mulm(mul, stir[n - 1][k]));
            stir[n][k] = v;
        }
    }

    for (auto [N, L, R] : qs) {
        if (L > R) {
            cout << 0 << '\n';
            continue;
        }

        int m = N - 1; // permutation tail length when y1=1
        int ans = 0;

        if (N == 1) {
            cout << ((L <= 1 && 1 <= R) ? 1 : 0) << "\n";
            continue;
        }

        // Count permutations with g(y)=0 (exactly those with y1 != 1)
        if (L <= 0 && 0 <= R) {
            int zeroCnt = (fact[N] - fact[m]) % MOD;
            if (zeroCnt < 0) zeroCnt += MOD;
            ans = addm(ans, zeroCnt);
        }

        // Positive g values are powers of 2: g = 2^t, t in [1..m]
        int loT, hiT;
        if (R < 2) {
            loT = 1;
            hiT = 0; // empty
        } else {
            loT = (L <= 1 ? 1 : ceil_log2_pos(L));
            hiT = floor_log2_pos(R);
        }

        if (loT <= hiT) {
            loT = max(loT, 1);
            hiT = min(hiT, m);
            if (loT <= hiT) {
                int sum = 0;
                for (int t = loT; t <= hiT; ++t) {
                    if (t <= KMAX) sum = addm(sum, stir[m][t]);
                }
                ans = addm(ans, sum);
            }
        }

        cout << ans << '\n';
    }
    return 0;
}

HackerRank Algebra – Permutation Equations