康托展开和逆康托展开

（康托展开）

#include <cstdio>

#include <string>
#include <cstring>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int fab[100];
int main(){
    string s;
    int k=0;

    cin>>s;
    int len=s.size();
    fab[0]=1;
    for(int i=1;i<100;i++) fab[i]=i*fab[i-1];
    for(int i=0;i<len;i++){
        int sum=0;
        for(int j=i+1;j<s.size();j++){
            if(s[j]<s[i]) sum++;
        }
        k+=fab[len-i-1]*sum;
    }
    printf("%d\n",k);
    //康托展开，已知一个字符串 求是第几个

    return 0;
}


#include <cstdio>
#include <string>
#include <cstring>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
int fab[100];
bool cmp(char x,char y){
    return x<y;
}
vector<char>v;
vector<char>re;
int main(){

    fab[0]=1;
    for(int i=1;i<100;i++) fab[i]=i*fab[i-1];

    int n,k;//n为这个字符串的位置，k为字符串的长度
    char s[100];
    scanf("%s",s);
    k=strlen(s);
    for(int i=0;i<k;i++) v.push_back(s[i]);
    scanf("%d",&n);
    for(int i=k;i>0;i--){
        int kk=n/fab[i-1];
        n%=fab[i-1];
        sort(v.begin(),v.end(),cmp);
        //printf("~~~%c\n",v[kk]);
        re.push_back(v[kk]);
        v.erase(v.begin()+kk);
    }
    for(int i=0;i<re.size();i++) printf("%c",re[i]);
    return 0;
}

//逆康托展开 已知是第几个 求字符串

//上述都是从0开始

（要注意题目是第几个，可能是从0开始或者从1开始）
（从1开始的话康托展开最后结果+1，
逆康托展开最后结果-1）