Submission #873925

#	Time	Username	Problem	Language	Result	Execution time	Memory
873925		noiaint	Cryptography (NOI20_crypto)	C++17	100 / 100	118 ms	15184 KiB

Crypto

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()

#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1 << (x))
#define popcount __builtin_popcountll

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long r) {
    return l + rd() % (r - l + 1);
}

const int N = 1e6 + 5;
const int mod = 1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int inf = 1e9; // INT_MAX;
const long long llinf = 1e18; // LLONG_MAX;

template<class X, class Y>
bool minimize(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}

template<class X, class Y>
bool maximize(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}

template<class X, class Y>
bool add(X &a, Y b) {
    a += b;
    while (a >= mod) a -= mod;
    while (a < 0) a += mod;
    return true;
}

int n;
int a[N];
int fac[N];
vector<int> temp;

int bit[N];
void update(int u, int c) {
    for (; u <= n; u += u & (-u)) bit[u] += c;
}
int get(int u) {
    int res = 0;
    for (; u > 0; u -= u & (-u)) res += bit[u];
    return res;
}

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

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        temp.push_back(a[i]);
    }
    sort(all(temp));
    for (int i = 1; i <= n; ++i)
        a[i] = lower_bound(all(temp), a[i]) - temp.begin() + 1;

    fac[0] = 1;
    for (int i = 1; i <= n; ++i) fac[i] = 1LL * fac[i - 1] * i % mod;

    for (int i = 1; i <= n; ++i) update(i, 1);

    int res = 0;

    for (int i = 1; i <= n; ++i) {
        int order = get(a[i]);
        add(res, 1LL * (order - 1) * fac[n - i] % mod);
        update(a[i], -1);
    }

    cout << (res + 1) % mod;

    return 0;
}

/*

[k, 1, 2,.., k - 1, k + 1,.., n]
-> (k - 1) * (n - 1)! ways

-> (order - 1) * (n - i)! ways

*/

• 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