51Nod 3209 康托展开

51Nod 3209 康托展开

给出一个排列（可能有重复数字），我们枚举由同样元素组成的所有不同排列，并将这些排列按照字典序从小到大排序，问当前排列排在第几位。

输入格式

第一行输入一个数t，表示测试数据的数量（1≤t≤100000） 之后对于每组数据， 第一行输入一个数n，表示排列中元素个数 （1≤n≤12） 第二行输入n个数ai，表示当前的排列（1≤ai≤12）

输出格式

输出共 t 行，对应排列排序的位置。

输入样例

3
3
1 2 3
3
2 1 2
3
2 1 3

输出样例

1
2
3

数据范围

对于15%的数据，1≤t≤5； 对于55%的数据，1≤t≤2000； 对于100%的数据，1≤t≤100000，1≤n≤12，1≤ai≤12；

在有重复的排列中如何做康托展开呢？约定元素为 an ，元素出现的次数为  。

那么元素的总数量为：

cnt1+cnt2+...tn=sum∑i=1ncnti=sumcnt1+cnt2+...tn=sum∑i=1ncnti=sum

首先我们考虑总的排列数量 totaltotal ，根据排列组合公式可知：

total=sum!/cnt1!/cnt2!..../cntn!total=sum!/cnt1!/cnt2!..../cntn!

以 1,1,2,2,2,31,1,2,2,2,3 为例，就是 6!/2!/3!/1!=606!/2!/3!/1!=60 个。

其中以 11 为首的排列 P1P1 ，共有 60/6∗2=2060/6∗2=20 个，其对应的公式为：

P1=total/sum∗cnt1Pn=total/sum∗cntnP1=total/sum∗cnt1Pn=total/sum∗cntn

我们计算 3,1,2,2,1,23,1,2,2,1,2 的排序位置，本质就是计算有多少个字典序小于他的排列，而所有以 1,21,2 为首的排列，均小于以 33为首的排列，我们利用上面给出的公式，对 1,21,2 这部分求和。

处理完第一个数字 33 后，问题转为了一个规模更小的问题，即：

由 1,1,2,2,21,1,2,2,2 组成的排列中， 1,2,2,1,21,2,2,1,2 的位置。采用同样的方法处理即可，其中的编程技巧，请参考标程实现。

参考程序

#include<bits/stdc++.h>
using namespace std;
int fact[15], nums[15], cnt[15];
void Init()
{fact[0] = 1;for(int i = 1; i <= 12; i++){fact[i] = fact[i - 1] * i;}
}
int main() {ios::sync_with_stdio(false);Init();int t, n;cin >> t;for(int i = 0; i < t; i++){memset(cnt, 0, sizeof(cnt));cin >> n;int total = fact[n];for(int j = 0; j < n; j++){cin >> nums[j];cnt[nums[j]]++;total /= cnt[nums[j]]; }int ans = 1;for(int j = 0; j < n; j++) {for(int k = 1; k < nums[j]; k++)ans += total * cnt[k] / (n - j);total = total * cnt[nums[j]] / (n - j);cnt[nums[j]]--;}cout << ans << endl;}return 0;
}