POJ_1850 Code【组合的运用】

题目：

Transmitting and memorizing information is a task that requires different coding systems for the best use of the available space. A well known system is that one where a number is associated to a character sequence. It is considered that the words are made only of small characters of the English alphabet a,b,c, ..., z (26 characters). From all these words we consider only those whose letters are in lexigraphical order (each character is smaller than the next character). 

The coding system works like this: 
• The words are arranged in the increasing order of their length. 
• The words with the same length are arranged in lexicographical order (the order from the dictionary). 
• We codify these words by their numbering, starting with a, as follows: 
a - 1 
b - 2 
... 
z - 26 
ab - 27 
... 
az - 51 
bc - 52 
... 
vwxyz - 83681 
... 

Specify for a given word if it can be codified according to this coding system. For the affirmative case specify its code. 

Input

The only line contains a word. There are some constraints: 
• The word is maximum 10 letters length 
• The English alphabet has 26 characters. 

Output

The output will contain the code of the given word, or 0 if the word can not be codified.

Sample Input

bf

Sample Output

55

题意分析：

对于不同的小写字母，严格升序组成的一组序列，分别代表从1~n的数值。

这题关键是求组合的数值C。对于方法，并不是太难，分两种情况

1.当长度小于给出的字符串L时，对于字符串长度为1的字符串总共代表的数字的量就是C(26,1)，对于长度为2的字符串总共代表的数字的量就是C(26,2)，一次类推，直到C(26,L-1)。

2.对于长度等于L的，从最开头的字符s[0]开始，对于比这个字符严格小的，如果有一个，我们可以有C('z'-s[0], L-1)个，'z'-s[0] 是因为题意已经说明该字符串每个位置是严格递增的。如果在这个位置，还能找到别s[0]严格小的，则再加上。

再遍历到后面的字符s[i],对于比这个字符严格小的，我们依然可以找到C('z'-s[0], L-i-1)个。一直到最后一个字符，这样，所有结果的总和，就是结果。

对于1中的原理如下：

以两位的串为例，有ab~az,bc~cz,……那么有组合数

递推出这个公式，需要结合组合里的一个很常用的式子

后面的依此类推。有大佬也指出，既然你是升序，那么只要你有几位，你就选几个出来，那么它的严格升序排列只有一种，所以就是C(26,L),就是在长度为L下的所有组合数。

然后利用上面的式子进行递推，求出所有的26以内的所有组合数，再直接利用求结果即可。

AC代码：

 

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;

LL C[27][27];
char S[15];

void getC()
{
    memset(C, 0, sizeof(C));
    for(int i = 0; i <= 26; i++)
    {
        for(int j = 0; j <= i; j++)
        {
            if(!j || i == j)
                C[i][j] = 1;
            else
                C[i][j] = C[i-1][j] + C[i-1][j-1];
        }
    }
    C[0][0] = 1;
}



int main()
{
    getC();

    while(~scanf("%s", S))
    {
        LL ans = 0;
        int len = strlen(S);

        //判断升序否
        for(int i = 1; i < len; i++)
        {
            if(S[i] <= S[i-1])
            {
                printf("0
");
                return 0;
            }
        }

        //先把长度比S小的数目都统计加起来
        for(int i = 1; i < len; i++)
        {
            ans += C[26][i];
        }

        //统计长度相同的，枚举相加
        for(int i = 0; i < len; i++)
        {
            int ch = i==0?'a':S[i-1]+1; //考虑到S升序
            for(; ch < S[i]; ch++)
            {
                ans += C['z' - ch][len - i - 1];  //从能选的字母中选出len-i+1个进行组合
            }
        }

        ans++;  //加自己

        printf("%lld
", ans);
    }
    return 0;
}