题目描述

（康托展开）求 $1\sim N$ 的一个给定全排列在所有 $1\sim N$ 全排列中的排名。结果对 $998244353$ 取模。

这里的排名指的是字典序第几小。

输入格式

第一行一个正整数 $N$。

第二行 $N$ 个正整数，表示 $1\sim N$ 的一种全排列。

输出格式

一行一个非负整数，表示答案对 $998244353$ 取模的值。

此程序可以处理 $1\le N\le 1000000$ 的全排列。

试补全程序。

思路提示：对于全排列的每一位，我们都需要去找这一位上还能放置的数字中 有几个比当前排列中这一位数字更小，然后去计算比给定全排列字典序小的全排列个数。

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
ll tree[1000005];
int n;
int lowbit(int x) {
	return ①;
}
void update(int x,int y) {
	while(x <= n){
		tree[x] += y;
		x += lowbit(x);
	}
}
ll query(int x) {
	ll sum = 0;
	while(x){
		sum += tree[x];
		x -= lowbit(x);	
	}
	return sum;
}
const ll lhm = 998244353;
ll jc[1000005] = {1, 1};
int a[1000005];
int main() {
	scanf("%d",&n);
	for(int i = 1; i <= n; i++) {
		jc[i] = (jc[i - 1] * i) % lhm;
		update(②);
	}
	ll ans = 0;
	for(int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		ans = (ans + ③ % lhm) % lhm;
		update(④);
	}
	printf("%lld", ⑤);
    return 0;
}

① 处应填

• A. x & -x
• B. x ^ (x - 1)
• C. x - (x & -x)
• D. x & (x - 1)

② 处应填

• A. $i, -1$
• B. $i, 1$
• C. 不需要这条语句
• D. $1, i$

③ 处应填

• A. query(a[i] - 1) * jc[n - i]
• B. (query(a[i]) - 1) * jc[i]
• C. query(a[i] - 1) * jc[i]
• D. query(a[i]) * jc[n - i]

④ 处应填

• A. i, 1
• B. a[i], 1
• C. a[i], -1
• D. i, -1

⑤ 处应填

• A. jc[n] - ans
• B. ans - 1
• C. ans
• D. ans + 1

输出格式

只有一行，为五个连续写出的大写字符，表示每个空你的选项。