题解 P5367 [模板]康托展开

发表于 | 阅读次数：

题面
康托展开是求排列排名的
对于从低到高的第$x$位(0~n-1)，贡献为

最后累和就好了
树状数组维护

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353, maxn = 1000010;
int fac[maxn], a[maxn], c[maxn], n;
inline int get(int x) {
    int ans = 0;
    for(; x; x -= x & (-x)) ans += c[x];
    return ans;
}
inline void add(int x, int k) {
    for(; x <= maxn; x += x & (-x)) c[x] += k;
}
int main() {
    scanf("%d", &n);
    fac[0] = 1;
    for(int i = 1; i < n; i++) fac[i] = 1ll * i * fac[i - 1] % mod;
    for(int i = 1; i <= n; i++) scanf("%d", a + i);
    int ans = 1;
    for(int i = n; i > 0; i--) {
        ans = (ans + 1ll * get(a[i]) * fac[n - i]) % mod;
        add(a[i], 1);
    }
    return printf("%d\n", ans), 0;
}