题目描述

给定1~N的一个全排列，试求它在所有1~N全排列中的排名。结果对998244353取模。

样例输入：             样例输出
3                     3
2 1 3

数据范围：
对于100%的数据，1 <= N <= 1e6;

解题思路

这道题要用到康托展开定理，并且直接暴力是不可行的
要对做法用树状数组进行优化

康托展开公式
定义及题解参考https://www.luogu.com.cn/problem/solution/P5367

代码

#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1000010, mod = 998244353;

ll fact[N], tr[N], ans, n;

ll lowbit(ll x)
{
    return x & (-x);
}

void add(int x, int v)
{
    for (int i = x; i <= n; i += lowbit(i))    tr[i] += v; 
}

ll query(ll x)
{
    ll res = 0;
    for (int i = x; i; i -= lowbit(i))  res += tr[i];
    return res;   
}

int main()
{
    scanf("%lld", &n);

    fact[0] = 1;
    for (int i = 1; i <= n; i++)  // 预处理阶乘
    {
        fact[i] = fact[i - 1] * i % mod;
        add(i, 1);
    } 

    for (ll i = 1, x; i <= n; i++)
    {
        scanf("%lld", &x);
        ll res = (query(x) - 1) * fact[n - i];
        ans = ans % mod + res % mod;
        add(x, -1);
    }

    printf("%lld", ans + 1);  // 加1是因为ans算的是所有比当前小的序列个数
    return 0;
}