本文共 1498 字，大约阅读时间需要 4 分钟。

为了求解给定全排列在所有全排列中的排名，我们采用康托展开和树状数组的方法。康托展开将问题分解为二进制位的处理，每个位的贡献累加即可得到逆序数。树状数组用于高效处理每个位的前缀和查询。

方法思路

解决代码

MOD = 998244353def main():    import sys    n_and_rest = list(map(int, sys.stdin.read().split()))    n = n_and_rest[0]    a = n_and_rest[1:n+1]    max_n = n    size = 1    while size < max_n:        size <<= 1    size <<= 1    tree = [0] * (size + 2)    def update(idx, val):        while idx <= size:            tree[idx] = (tree[idx] + val) % MOD            idx += idx & -idx    def query(idx):        res = 0        while idx > 0:            res = (res + tree[idx]) % MOD            idx -= idx & -idx        return res    inv_size = [0] * (size + 2)    for i in range(size):        inv_size[i] = pow(size, MOD-2, MOD) * pow(i, MOD-2, MOD) % MOD    inv = [0] * (n + 2)    for i in range(n+1):        inv[i] = pow(i, MOD-2, MOD)    res = 0    for num in a:        power = 1        for k in range(30, -1, -1):            if num & (1 << k):                cnt = query(1 << k) - query(num & ((1 << k) - 1))                res = (res + cnt * power) % MOD                power = (power * 2) % MOD            else:                power = (power * 2) % MOD        update(num, 1)    print((res + 1) % MOD)if __name__ == "__main__":    main()

代码解释

该方法高效地处理了大规模数据，确保了算法在时间和空间上的可行性。

转载地址：http://piqp.baihongyu.com/