Cerinta completa

Alice was given the integers from to . She wrote all possible permutations in increasing lexicographical order, and wrote each permutation in a new line. For example, for , there are possible permutations:

She then chose one permutation among them as her favorite permutation.

After some time, she forgot some elements of her favorite permutation. Nevertheless, she still tried to write down its elements. She wrote a in every position where she forgot the true value.

She wants to know the sum of the line numbers of the permutations which could possibly be her favorite permutation, i.e., permutations which can be obtained by replacing the s. Can you help her out?

Since the sum can be large, find it modulo .

Input Format

The first line contains a single integer .

The next line contains space-separated integers denoting Alice’s favorite permutation with some positions replaced by .

Constraints

  • The positive values appearing in are distinct.

Subtask

  • For ~33% of the total points,

Output Format

Print a single line containing a single integer denoting the sum of the line numbers of the permutations which could possibly be Alice’s favorite permutation.

Sample Input 0

4
0 2 3 0

Sample Output 0

23

Explanation 0

The possible permutations are and . The permutation occurs on line and the permutation occurs on line . Therefore the sum is .

Sample Input 1

4
4 3 2 1

Sample Output 1

24

Explanation 1

There is no missing number in the permutation. Therefore, the only possible permutation is , and it occurs on line . Therefore the sum is .

Limbajul de programare folosit: cpp20

Cod:

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

static const long long MOD = 1000000007LL;

struct Fenwick {
    int n;
    vector<int> bit;
    Fenwick(int n = 0) : n(n), bit(n + 1, 0) {}

    void add(int idx, int val) {
        for (; idx <= n; idx += idx & -idx) bit[idx] += val;
    }

    int sumPrefix(int idx) const {
        int s = 0;
        for (; idx > 0; idx -= idx & -idx) s += bit[idx];
        return s;
    }
};

long long modNorm(long long x) {
    x %= MOD;
    if (x < 0) x += MOD;
    return x;
}

long long modMul(long long a, long long b) {
    return (long long)((__int128)a * b % MOD);
}

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

    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<long long> fact(n + 1, 1);
    for (int i = 1; i <= n; i++) fact[i] = modMul(fact[i - 1], i);

    vector<int> used(n + 1, 0);
    int k = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] == 0) {
            k++;
        } else {
            used[a[i]] = 1;
        }
    }

    vector<int> prefMissing(n + 1, 0);
    long long sumMissingMinus1 = 0;
    for (int v = 1; v <= n; v++) {
        prefMissing[v] = prefMissing[v - 1] + (!used[v]);
        if (!used[v]) sumMissingMinus1 += (v - 1);
    }
    sumMissingMinus1 = modNorm(sumMissingMinus1);

    long long sumR = modNorm(1LL * k * (k - 1) / 2);
    long long ans = fact[k];

    Fenwick fw(n);
    int zpre = 0;
    long long sumKLOverMissing = 0;

    for (int i = 1; i <= n; i++) {
        long long C = 0;
        int rem = n - i;

        if (a[i] != 0) {
            int v = a[i];
            long long base = modNorm((v - 1) - fw.sumPrefix(v - 1));

            if (k == 0) {
                C = base;
            } else {
                long long term1 = modMul(fact[k], base);
                long long rv = prefMissing[v - 1];
                long long term2 = modMul(modMul(fact[k - 1], zpre), rv);
                C = modNorm(term1 - term2);
            }
        } else {
            if (k == 1) {
                C = modNorm(sumMissingMinus1 - sumKLOverMissing);
            } else {
                long long term1 = modMul(fact[k - 1], modNorm(sumMissingMinus1 - sumKLOverMissing));
                long long term2 = 0;
                if (k >= 2) {
                    term2 = modMul(modMul(fact[k - 2], zpre), sumR);
                }
                C = modNorm(term1 - term2);
            }
        }

        ans = modNorm(ans + modMul(fact[rem], C));

        if (a[i] == 0) {
            zpre++;
        } else {
            int v = a[i];
            int missGtV = k - prefMissing[v];
            sumKLOverMissing = modNorm(sumKLOverMissing + missGtV);
            fw.add(v, 1);
        }
    }

    cout << ans << endl;
    return 0;
}

Scor obtinut: 1.0

Submission ID: 464637689

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

Cards Permutation