Submission #255321

#	Time	Username	Problem	Language	Result	Execution time	Memory
255321		model_code	Cryptography (NOI20_crypto)	C++17	100 / 100	177 ms	6328 KiB

Crypto

#include <iostream>
#include <algorithm>
using namespace std;

const long long MOD = 1e9 + 7;
long long F[300010] = {1};
long long ANS = 1;
int N;
int P[300010], P2[300010];

int FT[300010];
void update(int X, int V) {
    for (; X <= N; X += X & -X)
        FT[X] += V;
}
int query(int X) {
    int RET = 0;
    for (; X; X -= X & -X)
        RET += FT[X];
    return RET;
}
void solve() {
    for (int a = 1; a <= N; ++a) {
        FT[a] += 1;
        int b = a + (a & -a);
        if (b <= N) FT[b] += FT[a];
    }
    for (int a = 1; a <= N; ++a) {
        (ANS += (query(P[a]) - 1) * F[N - a]) %= MOD;
        update(P[a], -1);
    }
    cout << ANS << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int a = 1; a <= N; ++a) {
        cin >> P[a];
        P2[a] = P[a];
    }
    sort(P2 + 1, P2 + N + 1);
    for (int a = 1; a <= N; ++a)
        P[a] = lower_bound(P2 + 1, P2 + N + 1, P[a]) - P2;
    for (int a = 1; a < N; ++a)
        (F[a] = F[a - 1] * a) %= MOD;
    solve();
    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