题解：P11319 [NOISG2020 Qualification] Cryptography

· · 题解

无聊缝合怪题。就是俩板子合一起了。

你会发现这些“随机打乱”和所谓的字典序，都是按照相对大小排序的。那么每个数具体是多少其实不重要，那么直接离散化。离散化完了之后就转换成了 【模板】康托展开，不会的可以去学习一下，此处直接贺板子即可。

时间复杂度瓶颈在离散化的排序和康托展开的树状数组。总时间复杂度 O(n\log n)。

#include <bits/stdc++.h>
using namespace std;
const int Mod = 1e9 + 7;
long long jc[1000005], tree[1000005], rk[1000005], n, ans = 1;
struct node { long long id,x;
    bool operator < (const node& y) const { return x < y.x; }
} a[1000005]; long long lowbit(long long x) { return x & (-x); }
long long sum(long long x) {
    long long ans = 0; while(x) ans += tree[x] % Mod, x -= lowbit(x);
    return ans % Mod;
} void add(long long x,long long k) {
    while(x <= n) tree[x] += k, x += lowbit(x);
} int main() { cin >> n; jc[0] = 1;
    for(int i = 1;i <= n;i++) cin >> a[i].x, a[i].id = i;
    sort(a+1,a+n+1); for(int i = 1;i <= n;i++) rk[a[i].id] = i;
    for(int i = 1;i <= n;i++) jc[i] = jc[i-1] * i % Mod, jc[i] %= Mod;
    for(int i = 1;i <= n;i++) add(i,1); for(int i = 1;i <= n;i++) {
        ans += ((sum(rk[i]) - 1) * jc[n-i] % Mod) % Mod; add(rk[i],-1);
    } cout << ans % Mod << endl;
    return 0;
}