康拓展开
给出一个全排列，求他是第几个全排列称为康拓展开。
暴力康拓展开
对于一个全排列来说，从左往右第i位，有 n + 1 - i 种选择。如果用变进制数表示的话，这一位就是 n + 1 - i 进制的数，如果这一位选择了第k种情况，那么对应的这一位就是k。(k从0开始）
比如：1 4 5 2 3 6 变成变进制数就是(022000）
- 首位1 是6种选择的第一种{1, 2, 3, 4, 5, 6}，所以变为0。
- 次位4 是5种选择的第三种{2, 3, 4, 5, 6}，所以变为2。
- 次位5 是4种选择的第三种{2, 3, 5, 6}，所以变为2。
- 次位2 是3种选择的第一种{2, 3, 6}，所以变为0。
- 次位3 是2种选择的第一种{3, 6}，所以变为0。
- 末位6 是1种选择的第一种{6}，所以变为0。
我们发现：第i位的值就是ai - 左边比它小的数的个数- 1。
for (int i = 1; i <= n; ++i){ cin >> a[i]; int x = a[i]; for (int j = 1; j <= a[i]; ++j) x -= vis[j]; vis[a[i]] = 1; a[i] = x - 1;} 之后把变进制数转化成10进制就可以了
ll res = 0;for (int i = 1; i < n; ++i) res = (res + a[i]) * (n - i);
最后的答案是 res + 1。
优化
刚才的算法复杂度有O(N ^ 2)，其实对于找左侧比ai小的数的时候，用树状数组维护一下就可以在log的时间内求出该值。
#includeusing namespace std;#define forn(i, n) for (int i = 0; i < (n); i++)#define forab(i, a, b) for (int i = (a); i <= (b); i++)#define forba(i, b, a) for (int i = (b); i >= (a); i--)#define mset(a, n) memset(a, n, sizeof(a))#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)#define N 1000005#define ll long longconst int Q = 998244353;int a[N], c[N], n;ll res;inline int lowbit(int x) { return x & (-x); }void add(int x,int d){ while(x <= n) { c[x] += d; x += lowbit(x); }}int sum(int x){ int s = 0; while(x) { s += c[x]; x -= lowbit(x); } return s;}int main(){ fast; cin >> n; forab(i, 1, n) { cin >> a[i]; add(a[i], 1); if(i < n) res = ((res + a[i] - sum(a[i] - 1) - 1) * (n - i)) % Q; } cout << (res + 1) << endl;}
(正在尝试手推逆向康拓展开。。。