题意
求 \(1\sim N\) 的一个给定全排列在所有 \(1\sim N\) 全排列中的排名。结果对 \(998244353\) 取模。
分析
模板，又学习了一种新的东西，但好像除了做这道体外，还不知道有什么用，呜呜。
先给式子。
\(ans=1+\sum_{i=1}^{n} A[i]\times(n-i)!\)
其中 \(A[i]\)代表 \(\sum_{j=i}^{n}[a[j] < a[i]]\)
怎么来理解这个式子呢？想象构造出字典序比当前排列小的有几个排列
枚举到 \(i\) 表示 \(1\) 到 \(i-1\) 和原来的排列一样， \(i\) 位肯定不一样，之后咋样都行。
既然到 \(i\) 位不一样，那么字典序大小其实就是取决于 \(i\) 位。很明显，第 \(i\) 位肯定要小于 \(a[i]\) 。然后只要把 \(i\) 后面小于 \(a[i]\) 的数交换到 \(i\) 位，后面随便排就行了。
很明显，这样枚举可以做到不重不漏。因为要求的是排名，所以 \(ans+=1\) 。
当然要用树状数组优化一下，复杂度是 \(O(nlgn)\) 的。
\(code\)
#include<bits/stdc++.h>
#define mod 998244353
#define int long long
#define N 1000005
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,ans=1;
int a[N],c[N],fac[N]={1,1};
void add(int x,int k){for(;x<=n;x+=x&(-x)) c[x]+=k;}
int ask(int x){int sum=0;for(;x;x-=x&(-x))sum+=c[x];return sum;}
signed main(){
n=read();
for(int i=1;i<=n;++i) a[i]=read();
for(int i=2;i<=n;++i) fac[i]=(fac[i-1]*i)%mod;
for(int i=n;i;--i){
ans=(ans+fac[n-i]*ask(a[i]))%mod;
add(a[i],1);
}
printf("%d\n",ans);
return 0;
}