前往：我自己搭建的博客
题目
洛谷P5367康托展开
题解
假设一个1~n的全排列，将其中一种排列看做一个数字，则可求出它在全排列中从小到大的排名X+1（X表示在它之前的排列个数）。a[i]表示这个排列的第i位（从右往左数）的数字右边有几个数字比它小。（例子：集合1~5，排列（3,4,2,5,1）3的右边有1,2，如果1,2在3的位置上，则可以分别产生（5-1）！种排列。）
求a[i]时需要用树状数组，注意此处的树状数组下标并不表示序列位置，而是数值。从排列的右侧到左侧统计，每次查询已在数组中的比当前位数字小的数的个数，然后再将当前位的数字加入到树状数组中。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=998244353;
const int maxn=1e6+5;
int n;
ll tmp=1,ans;
ll num[maxn],sum[maxn];
inline int lowbit(int x) {return x&(-x);}
inline void add(int x) {for( ;x<=n;x+=lowbit(x)) sum[x]++;}
inline ll ask(int x) {ll ans=0; for( ;x;x-=lowbit(x)) ans+=sum[x]; return ans;}
inline ll cnt(int x) {return ask(num[x]);} //求位置x处数字右侧更小数的数量
inline void solve()
{
add(num[1]);
for(ll i=2;i<=n;i++)
{
tmp=tmp*(i-1)%MOD;
ans=(ans+cnt(i)*tmp%MOD)%MOD;
add(num[i]);
}
printf("%lld\n",ans+1); //注意+1
}
int main()
{
scanf("%d",&n);
for(int i=n;i>=1;i--) scanf("%lld",&num[i]); //倒序输入
solve();
return 0;
}
