【模板题】康托展开

【题目链接】

点击打开链接

【题目概括】

请计算给定排列的字典序的大小。
答案对998244353取模。
数据规模：n\leq 10^6。

【思路要点】

• 康托展开的公式为Rank=\sum cnt_i\times (n-i+1)!。
• 其中cnt_i表示第i位后有多少位的数值小于第i位。
• 转化成树状数组求逆序对的模型。

【代码】

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

template <class T> 
void read(T &x) {
  x = 0; char ch = 0; int f = 1; 
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
  x *= f;
}

template <class T>
void pr(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) pr(x / 10);
  putchar(x % 10 + 48);
}

void ps() {
  puts("");
}

const int MOD = 998244353;
const int N = 1e6 + 5;

struct _fenwick {
  int lowbit(int x) {
    return x & -x;
  }
  int tr[N];
  int n;
  void setLim(int lim) {
    n = lim;
  }
  void modify(int p, int v) {
    for (; p <= n; p += lowbit(p))
      tr[p] += v;
  }
  int query(int p) {
    int ans = 0;
    for (; p; p -= lowbit(p))
      ans += tr[p];
    return ans;
  }
} bit1;

int fac[N];

int contor(const vector<int>& p) {
  fac[0] = 1ll;
  int len = p.size(), ans = 0;
  for (int i = 1; i <= len; i++)
    fac[i] = (ll)fac[i - 1] * i % MOD;
  bit1.setLim(len);
  for (int i = len - 1; i >= 0; i--) {
    int cnt = bit1.query(p[i]);
    ans = ((ll)ans + (ll)cnt * fac[len - i - 1]) % MOD;
    bit1.modify(p[i], 1);
  }
  return (ans + 1) % MOD;
}

int main() {
  int n; 
  read(n);
  vector<int> a;
  for (int i = 1; i <= n; i++) {
    int x;
    read(x);
    a.push_back(x);
  }
  pr(contor(a)), ps();
  return 0; 
}