Submission #947198

---

Source Code Expand

#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <queue>
#include <ctime>
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <bitset>

using namespace std;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define epr(...) fprintf(stderr, __VA_ARGS__)
#define db(x) cerr << #x << " = " << x << endl
#define db2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")\n"; 
#define db3(x, y, z) cerr << "(" << #x << ", " << #y << ", " << #z << ") = (" << x << ", " << y << ", " << z << ")\n"
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()

#define equal equalll
#define less lesss
typedef long long ll;
const int N = 5e5 + 10;
const long long INF = 1e9 + 19;
const int MOD = 1e9 + 7;

int n;
int a[N];
ll fact[N];
bool use[N];
int tree[N];

void read() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        a[i]--;
    }
}

int get(int r) {
    int sum = 0;
    for (; r > 0; r &= (r - 1))
        sum += tree[r];
    return sum;
}

void add(int pos, int val) {
    for (; pos <= n; pos |= (pos + 1))
        tree[pos + 1] += val;
}

ll solve() {
    fact[0] = 1;
    for (int i = 0; i <= n; i++)
        tree[i] = 0;
    for (int i = 1; i <= n; i++)
        fact[i] = (fact[i - 1] * i) % MOD;
    for (int i = 0; i < n; i++)
        use[i] = 0;

    for (int i = 0; i < n; i++)
        if (a[i] != -1)
            use[a[i]] = 1;
    vector<int> b;
    for (int i = 0; i < n; i++)
        if (!use[i])
            b.pb(i);

    ll answer = 0;  

    ll cntEmpty = 0;
    ll m = b.size();
    ll superCnt = 0;
    for (int i = n - 1; i >= 0; i--) {
        ll w = fact[n - i - 1];
        if (a[i] >= 0) {
            ll cnt = get(a[i]);
            answer = (answer + w * cnt % MOD * fact[b.size()]) % MOD;
            add(a[i], 1);

            ll t = lower_bound(all(b), a[i]) - b.begin();
            if (cntEmpty > 0)
                answer = (answer + t * 1ll * cntEmpty % MOD * fact[(int)b.size() - 1] % MOD * w) % MOD;
            superCnt = (superCnt + (m - t)) % MOD;
        }
        else {
            if (cntEmpty > 0) {
                ll par = (m * 1ll * (m - 1) / 2) % MOD;
                answer = (answer + fact[m - 2] * cntEmpty % MOD * par % MOD * w) % MOD;
            }
            answer = (answer + w * superCnt % MOD * fact[m - 1]) % MOD;
            cntEmpty++;
        }
    }

    answer = (answer + fact[b.size()]) % MOD;

    return answer;

}

ll stupid() {
    vector<int> perm;
    for (int i = 0; i < n; i++)
        perm.pb(i);
    int fact = 1;
    for (int i = 1; i <= n; i++)
        fact = (fact * i) % MOD;
    ll answer = 0;
    for (int i = 1; i <= fact; i++) {
        //if (i % 10000 == 0)
            //db(i);
        bool good = 1;
        for (int j = 0; j < n; j++)
            if (a[j] != -1)
                good &= perm[j] == a[j];
        
        if (good)
            answer = (answer + i) % MOD;
        next_permutation(all(perm));
    }
    return answer;

}

void genTest() {
    n = 5;
    for (int i = 0; i < n; i++)
        a[i] = i;
    random_shuffle(a, a + n);
    for (int i = 0; i < n; i++)
        if (rand() % 2 == 0)
            a[i] = -1;
}

void stress() {
    for (int tt = 0; ; tt++) {
        db(tt);
        genTest();
        auto r1 = solve();
        auto r2 = stupid();
        db2(r1, r2);
        if (r1 != r2) {
            cout << n << endl;
            for (int i = 0; i < n; i++)
                cout << a[i] + 1 << " ";
            cout << endl;
        }
        assert(r1 == r2);
    }

}


int main(){
#ifdef MY_DEBUG
    freopen("in", "r", stdin);
    //freopen("out", "w", stdout);
#endif
    if (1) {
        int k = 1;
        for (int tt = 0; tt < k; tt++) {
            read();
            cout << solve() << endl;
            //cout << stupid() << endl;
        }
    }
    else {
        stress();
    }

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void read()’:
./Main.cpp:44:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
./Main.cpp:46:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
                           ^

Judge Result