题面
康托展开是求排列排名的
对于从低到高的第$x$位(0~n-1),贡献为
最后累和就好了
树状数组维护
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
|
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; }
|
近期评论