特殊算法技巧|康托展开简单记录 c++|算法|动态规划|数学

作用

求一个 [ 1 , n ] [1,n] [1,n]按照字典序从小到大排列的排名

例题 https://www.luogu.com.cn/problem/P5367
过程

以 { 1 , 2 , 3 , 4 , 5 } \{1,2,3,4,5\} {1,2,3,4,5}为排名为1的序列，那么 { 1 , 2 , 3 , 5 , 4 } \{1,2,3,5,4\} {1,2,3,5,4}就是排名为2的排列，考虑一下如何求 { 5 , 1 , 4 , 3 , 2 } \{5,1,4,3,2\} {5,1,4,3,2}
将数子逐个分析，考虑字典序，因为第一个5右侧有四个比它字典序小的数，每一个数开头都有 4 ! 4! 4!种排列方式，所以这个数对答案的贡献是 4 × 4 ! 4\times 4! 4×4!；第二个1前面没有数；第三个4右侧有2个比它小的数，每一个数开头都有 2 ! 2! 2!种排列方式，这个数对答案的贡献为 2 × 2 ! 2\times 2! 2×2!；同理第四个数1对答案的贡献为 1 × 1 ! 1\times 1! 1×1!；第五个数对答案的贡献为 0 × 0 ! 0\times 0! 0×0!，所以总共贡献和为 4 × 4 ! + 2 × 2 ! + 1 × 1 ! = 101 4\times 4!+2\times 2!+1\times 1!=101 4×4!+2×2!+1×1!=101，所以它的名次就是102
那么容易写出 O ( n 2 ) O(n^2) O(n2)的程序

#include using namespace std; typedef long long ll; const int MOD = 998244353; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; vector fac(n + 1), a(n + 1); for(int i=1; i<=n; i++) cin >> a[i]; fac[0] = 1; for(int i=1; i<=n; i++) fac[i] = 1ll * fac[i - 1] * i % MOD; int ans = 1; for(int i=1; i a[j]) k += 1; } ans = (1ll * ans + 1ll * k * fac[n - i]) % MOD; } cout << ans; return 0; }

那显然中间的 n n n次循环就是求一个后缀逆序对，可以树状数组优化到 O ( n l o g n ) O(nlogn) O(nlogn)

#include using namespace std; typedef long long ll; const int MOD = 998244353; const int N = 1e6 + 100; int tree[N]; int n; int lowbit(int x){ return x & -x; } void modify(int x, int d){ while(x <= n){ tree[x] += d; x += lowbit(x); } } int query(int x){ int ans = 0; while(x > 0){ ans += tree[x]; x -= lowbit(x); if(ans >= MOD) ans %= MOD; } return ans; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; vector fac(n + 1), a(n + 1); for(int i=1; i<=n; i++) cin >> a[i]; fac[0] = 1; for(int i=1; i<=n; i++) fac[i] = 1ll * fac[i - 1] * i % MOD; int ans = 1; for(int i=1; i<=n; i++){ ans = (1ll * ans + 1ll * (a[i] - 1 - query(a[i])) * fac[n - i]) % MOD; modify(a[i], 1); } cout << ans; return 0; }