算法
(康托展开、树状数组) $O(n\log n)$
似乎康托展开已经烂大街了
先来看一下康托展开的式子:
$ \sum\limits_{i=1}^N\sum\limits_{j=i+1}^N [a_i > a_j] \cdot (n-i)! $
显然暴力 $O(N^2)$ 做法肯定过不了
注意到,$a_i > a_j (i < j)$ 是一对逆序对,所以我们可以用树状数组来维护
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
using ll = long long;
const int mod = 998244353;
// const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
template<typename T>
struct BIT {
int n;
vector<T> d;
BIT(int n=0):n(n),d(n+1) {}
void add(int i, T x=1) {
for (i++; i <= n; i += i&-i) {
d[i] += x;
}
}
T sum(int i) {
T x = 0;
for (i++; i; i -= i&-i) {
x += d[i];
}
return x;
}
T sum(int l, int r) {
return sum(r-1) - sum(l-1);
}
};
int p[1000005];
mint fact[1000005];
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int n;
cin >> n;
rep(i, n) cin >> p[i];
fact[0] = 1;
rep(i, n) fact[i] = fact[i-1]*i;
mint ans = 1;
BIT<ll> t(n+1);
rep(i, n) {
mint now = p[i]-1-t.sum(p[i]);
ans += now*fact[n-i];
t.add(p[i]);
}
cout << ans << '\n';
return 0;
}