题目大意：给定一个$n$的排列，求它在$n$的全排列中的名次
题解：康托展开，对于一个全排列，第$i$为有$n+1-i$种选择，用变进制数表示，这一位就是$n+1-i$进制。记排列中第$[1,i)$中比第$i$位小的数个数位$a$，变进制数中第$i$位的数为$i-a-1$。可以用树状数组维护
卡点：无
C++ Code：
#include#include #include #define maxn 1000010#define mul(a, b) (static_cast (a) * (b) % mod)const int mod = 998244353;inline void reduce(int &x) { x += x >> 31 & mod; }int fac[maxn], ans = 1, n;namespace BIT { int V[maxn], res; inline void add(int p) { for (; p <= n; p += p & -p) ++V[p]; } inline int query(int p) { for (res = 0; p; p &= p - 1) res += V[p]; return res; }}int main() { std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0); std::cin >> n; fac[0] = 1; for (int i = 1; i <= n; ++i) fac[i] = mul(fac[i - 1], i); for (int i = 1, x; i <= n; ++i) { std::cin >> x; reduce(ans += mul(x - BIT::query(x) - 1, fac[n - i]) - mod); BIT::add(x); } std::cout << ans << '\n'; return 0;}