康托展开简单记录

简单记录"/>

康托展开简单记录

作用

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

例题

过程

• 以 { 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 <bits/stdc++.h>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<int> 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++){int k = 0;for(int j=i+1;j<=n;j++){if(a[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 <bits/stdc++.h>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<int> 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;
}

• 在解决一些搜索问题比如八数码问题时，可以使用康托展开来记录出现过的状态