题解 p5367 [模板]康托展开

using namespace std;
const int mod = 998244353, maxn = 1000010;
int fac[maxn], a[maxn], c[maxn], n;
inline int (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("%dn", ans), 0;
}