51 lines
1.5 KiB
C++
51 lines
1.5 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
string str;
|
||
int ans;
|
||
|
||
//求组合数的优化后办法
|
||
long long C(int n, int m) {
|
||
long long sum = 1;
|
||
for (int i = 1; i <= m; i++)
|
||
sum = sum * (n - m + i) / i;
|
||
return sum;
|
||
}
|
||
|
||
/**
|
||
* 测试用例：cgx
|
||
* 答案：1007
|
||
* @return
|
||
*/
|
||
int main() {
|
||
//输入字符串
|
||
cin >> str;
|
||
//字符串长度
|
||
int len = str.size();
|
||
|
||
//判断是否合法
|
||
for (int i = 0; i < len; i++)
|
||
if (str[i] <= str[i - 1]) {//非升序就是不正确的编码
|
||
cout << 0;
|
||
exit(0);
|
||
}
|
||
|
||
//1、计算出位数比它小的单词数
|
||
//比如是cgx,那么就计算出
|
||
// 1位的有C(26,1)个
|
||
// 2位的有C(26,2)个
|
||
for (int i = 1; i < len; i++)ans += C(26, i);
|
||
|
||
//2、到这就是位数和它自己一样的了
|
||
// 枚举每一位,从低到高，一个个来
|
||
for (int pos = 0; pos < len; pos++) {
|
||
//每一位都要找到比当前输入字符串小的字符串个数，叠加在一起就是结果
|
||
char start = 'a';//初值为`a`,首位的话，从`a`开始，其它的从上一位的后面一个开始
|
||
if (pos > 0)start = str[pos - 1] + 1; //str的数组下标是从0开始的
|
||
for (char j = start; j < str[pos]; j++)//注意范围,找比它小的
|
||
ans += C('z' - j, len - pos - 1); //'z' - j 剩下可用的字符数量, len-pos-1需要选择的字符数量
|
||
}
|
||
//别忘了最后把自己加上
|
||
cout << ++ans;
|
||
return 0;
|
||
} |