Submission #737437

#	Time	Username	Problem	Language	Result	Execution time	Memory
737437		Ronin13	Cryptography (NOI20_crypto)	C++14	100 / 100	392 ms	61232 KiB

Crypto

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 10000001;
vector <int> bit(nmax);

const ll mod = 1e9 + 7;

int lsb(int x){
    return x & -x;
}

void add(int pos, int v, int n){
    while(pos <= n){
        bit[pos] += v;
        pos += lsb(pos);
    }
}

int get(int pos){
    int res = 0;
    while(pos){
        res += bit[pos];
        pos -= lsb(pos);
    }
    return res;
}

int main(){
    int n; cin >> n;
    int p[n + 1];
    for(int i = 1; i <= n ;++i)
        cin >> p[i];
    map <int,int> mp;
    int b[n + 1];
    for(int i = 1;i <= n ;i++){
        b[i] = p[i];
    }
    sort(b + 1, b + 1 + n);
    for(int i = 1; i <= n; i++){
        mp[b[i]] = i;
    }
    for(int i = 1; i <= n; ++i){
        add(i, 1, n);
        p[i] = mp[p[i]];
    }
    ll fact[n + 1];
    fact[0] = 1;
    for(int i = 1; i <= n; i++){
        fact[i] = fact[i - 1] * (ll)i % mod;
    }
    ll curans = 1;
    for(int i = 1; i <= n; i++){
        int x = p[i];
        ll o = get(x - 1);
        curans += fact[n - i] * o;
        curans %= mod;
        add(x, -1, n);
    }
    cout << curans << "\n";
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 9 / 9
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 21 / 21
• Subtask 6: 13 / 13
• Subtask 7: 19 / 19
• Subtask 8: 12 / 12