组合数,
给一个字符串, 这个字符串必须为字典序升序,否则输出0,
求这个字符串排列在第几个;
距离 a = 1 ; b=2.... ab=27 ac=28.... ba不可以 az=51, bc = 52..... 长度不超过10
那么首先特盘递增,其次这个字符串是升序,所以对于长度 n 的 我们可以先加上 C[26] [ n - 1 ] C 代表组合数
26个字母先选出 n-1 个,之后对 n 长度开始处理
每次暴力搜素,因为 只有 26个字母,对于第 i 位, 搜索 s [i-1] - z ,进行一波组合数计算, 第一位 从 a 开始 每次都是
加上 c[ 26- s[i-1] ] [ strlen(s) - i - 1 ] 就好了
以下为 AC 代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn=1e5+5;
#define ll long long int
ll c[30][30];
void combine()
{for(int j=0;j<=26;j++)for(int i=0;i<=j;i++)if(!j||i==j)c[j][i]=1;elsec[j][i]=c[j-1][i-1]+c[j-1][i];
}
char s[20];
int main()
{combine();scanf("%s",s);int len = strlen(s);int ans = 0;for(int i=1;i<len;i++){if(s[i]<=s[i-1]){printf("0\n");return 0;}}int sum=0;for(int i=1;i<len;i++)sum+=c[26][i];int st = 1;for(int i=0;i<len;i++){int en = s[i]-'a'+1;for(int j=st;j<en;j++){sum += c[26-j][len-(i+1)];}st = en+1;}printf("%d\n",sum+1);return 0;
}