康托展開就是指當(dāng)前n個元素的排列在這n個元素的全排列里的排名(從小到大) 逆康托展開就是已知某排列在全排列的排名，求這個排列
那么對于n個數(shù)來說，康托展開為：
，在這個公式中an表示第i個元素在未出現(xiàn)的元素中排第幾。如：對于507來說，5在507中排第1（從0開始），0在07中排第0,7排第0即a3=1,a2=0,a1=0，這樣得到507在所有排列中ans=2(從零開始)
代碼實(shí)現(xiàn)：
ll h[maxn]; //階乘數(shù)組void init(int n){ h[0] = 1; for(ll i=1;i<n;i++) h[i] = h[i-1]*i;}ll slove(char a[]){ //康托定理 int len = strlen(a); ll res = 0; for(int i=0;i<len;i++) { int tmp = 0; for(int j=i+1;j<len;j++) { if(a[i]>a[j]) tmp++; } res += tmp*h[len-i-1]; } return res;}新聞熱點(diǎn)
疑難解答
