P5367 【模板】康托展开【树状数组优化】

题目链接

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const ll mod = 998244353;
const int maxN = 1e6 + 7;
int trie[maxN], N;
inline void add(int i)
{
    while(i <= N)
    {
        trie[i]++;
        i += lowbit(i);
    }
}
inline ll query(int x)
{
    ll ans = 0;
    while(x)
    {
        ans += trie[x];
        x -= lowbit(x);
    }
    return ans;
}
ll jc[maxN];
ll Cantor(int len, int *a)
{
    ll tmp, ans = 0;
    for(int i=len-1; i>=0; i--)
    {
        tmp = query(a[i]);
        ans += tmp * jc[len - i - 1]%mod;
        ans %= mod;
        add(a[i]);
    }
    return (ans + 1) % mod;
}
int s[maxN];
int main()
{
    jc[0] = jc[1] = 1;
    for(ll i=2; i<maxN; i++) jc[i] = jc[i-1] * i % mod;
    scanf("%d", &N);
    for(int i=0; i<N; i++) scanf("%d", &s[i]);
    printf("%lld\n", Cantor(N, s));
    return 0;
}