POJ1850 Code（组合+康托展开）
题目问一个合法字符串的字典序是第几个，合法的字符串是指里面的字符严格递增。
先判断合不合法，然后用类似康托展开的过程去求。大概过程就是用组合数算出某长度某前缀有几个，累加起来。
真难一遍写对。。
1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 bool islegal(char *s){ 5 for(int i=1; s[i]; ++i){ 6 if(s[i]<=s[i-1]) return 0; 7 } 8 return 1; 9 } 10 long long C[27][27]; 11 int main(){ 12 for(int i=0; i<27; ++i) C[i][0]=1; 13 for(int i=1; i<27; ++i){ 14 for(int j=1; j<=i; ++j) C[i][j]=C[i-1][j]+C[i-1][j-1]; 15 } 16 char str[11]; 17 scanf("%s",str); 18 if(!islegal(str)){ 19 puts("0"); 20 return 0; 21 } 22 int len=strlen(str); 23 long long res=0; 24 for(int i=1; i<len; ++i) res+=C[26][i]; 25 bool vis[26]={0}; 26 for(int i=0; i<len; ++i){ 27 int j=i==0?0:str[i-1]-'a'; 28 for(; j<str[i]-'a'; ++j){ 29 if(vis[j]) continue; 30 int cnt=0; 31 for(int k=j+1; k<26; ++k){ 32 if(!vis[j]) ++cnt; 33 } 34 res+=C[cnt][len-i-1]; 35 } 36 vis[str[i]-'a']=1; 37 } 38 printf("%lld",res+1); 39 return 0; 40 }