测试链接
题目描述
求 \(1\sim N\) 的一个给定全排列在所有 \(1\sim N\) 全排列中的排名。结果对 \(998244353\) 取模。
输入格式
第一行一个正整数 \(N\)。
第二行 \(N\) 个正整数，表示 \(1\sim N\) 的一种全排列。
输出格式
一行一个非负整数，表示答案对 \(998244353\) 取模的值。
输入输出样例 #1
输入 #1
3
2 1 3
输出 #1
3
输入输出样例 #2
输入 #2
4
1 2 4 3
输出 #2
2
说明/提示
对于 \(10\%\) 数据，\(1\le N\le 10\)。
对于 \(50\%\) 数据，\(1\le N\le 5000\)。
对于 \(100\%\) 数据，\(1\le N\le 1000000\)。
公式
设有一个由数字 (1,2,\dots,n) 组成的排列
\((a_1, a_2, \dots, a_n) ,\)
定义对每个位置 \(i\) ：
\(c_i = \{\, j \mid j > i,\ a_j < a_i \,\}\),
即 \(c_i\) 是在第 \(i\) 个元素之后、且比 \(a_i\) 小的元素个数。
则该排列的康托展开值为
\(\mathrm{Cantor}(a_1, a_2, \dots, a_n) = \sum_{i=1}^{n} c_i \cdot (n-i)!\)
其中
\(0 \le c_i \le n - i,\quad i = 1,2,\dots,n\)
思路
数据量1e6很大，不能按照公式计算直接暴力枚举，所以我们可以考虑使用树状数组求取比当前\(a_i\)小的数，那么\(a_i\) 减去当前小于\(ai\)的就是后面出现的小于\(ai\)的个数，那么我们就可以在 \(O(nlogn)\) 的时间复杂度内求解
题解
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const int mod = 998244353 ;
typedef long long ll;
int n;
ll a[N];
ll fac[N];ll tree[N];int lowbit(int i)
{return i&-i;
}void add(int i,int v)
{while(i<=n){tree[i]+=v;i += lowbit(i);}
}ll query(int i)
{int sum = 0;while(i>0){sum += tree[i];i -= lowbit(i);} return sum;
}void solve()
{cin>>n;ll res = 0;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){ll cnt = query(a[i]);cnt = a[i]-cnt-1;res += fac[n-i]*cnt%mod;res %= mod;add(a[i],1);}res = (res+1)%mod;cout<<res<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);fac[0]=1;for(int i=1;i<=N-10;i++){fac[i] = fac[i-1]*i%mod;}int t=1;// cin>>t;while(t--){solve();}return 0;
}
