HackerRank Combinatorics – Value of all Permutations

Challenge: Value of all Permutations

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 80.0 / 80

Submission status: Accepted

Submission score: 1.0

Submission ID: 464762597

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/value-of-all-permutations/problem

Cerinta

You are given an array $A$ of size $N$. You are asked to answer $Q$ queries.  

Each query contains a number $M$.  

For each *distinct* permutation of the array $A$, you need to print the sum of the values returned by the `find` function.

As the sum can be too large, output it modulo $P$, which is a prime and given in input.  

	find(int permutation_A[], int M)
	{
        x = Length(permutation_A)
        sum = 0
        for(i = 0; i < x; i++) {
        	if (permutation_A[i] <= M)
            	sum = sum + permutation_A[i]
            else
            	break
		}
		return sum
    }


**Input Format**  
The first line of input contains $P$.  
The second line of input contains $N$. The next line contains $N$ numbers $A[0] \ldots A[N-1]$ separated by single spaces.  
The next line contains $Q$, the number of queries to follow. Each subsequent line contains one positive integer $M$.  

**Output Format**  
For each query, output as asked above.  

**Constraints**  
$1000000 \le P \le 2000003$  
$1 \le N \le 10^5$  
$1 \le Q \le 10^5$  
$1 \le A[i], M \le 10^9$

**Sample Input**

	2000003
	5
	4 2 3 1 4
	2
	1
	2

**Sample Output**

	12
    45
    
**Explanation**

*Query 1*:  
Consider all permutations. if the first number is greater than 1, then the loop will break in the beginning itself. There are a total of 60 distinct permutations out of which 48 will give 0. The remaining 12 will fetch 1 each from the function. Thus the answer is 12.

Cod sursa

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

long long modpow(long long a, long long e, long long mod) {
    long long r = 1 % mod;
    a %= mod;
    if (a < 0) a += mod;
    while (e > 0) {
        if (e & 1LL) r = (__int128)r * a % mod;
        a = (__int128)a * a % mod;
        e >>= 1LL;
    }
    return r;
}

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

    long long P;
    cin >> P;

    int N;
    cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    vector<long long> fact(N + 1, 1 % P);
    for (int i = 1; i <= N; ++i) fact[i] = (__int128)fact[i - 1] * i % P;

    unordered_map<long long, int> cnt;
    cnt.reserve(N * 2 + 1);
    for (auto x : A) cnt[x]++;

    long long total_perm = fact[N];
    for (auto &kv : cnt) {
        total_perm = (__int128)total_perm * modpow(fact[kv.second], P - 2, P) % P;
    }

    sort(A.begin(), A.end());
    vector<long long> pref(N + 1, 0);
    for (int i = 0; i < N; ++i) {
        long long v = A[i] % P;
        if (v < 0) v += P;
        pref[i + 1] = pref[i] + v;
        if (pref[i + 1] >= P) pref[i + 1] -= P;
    }

    int Q;
    cin >> Q;
    while (Q--) {
        long long M;
        cin >> M;

        int s = upper_bound(A.begin(), A.end(), M) - A.begin();
        if (s == 0) {
            cout << 0 << '\n';
            continue;
        }

        long long W = pref[s];
        long long den = N - s + 1; // always >=1
        long long ans = total_perm;
        ans = (__int128)ans * W % P;
        ans = (__int128)ans * modpow(den, P - 2, P) % P;

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

    return 0;
}