ACM 417 Word Index

排列組合的題目
提供大家一個思考方向，如何計算abcde呢？
abcde前面有長度為1~4的words
長度為4的words有C(26, 4)個 (因為要遞增)
其他依此類推
當然abcde是很簡單的情況
可以試著想看看bdgh的計算方式，想出來這題就結束了


#include <stdio.h>
#include <string.h>

int C[26+1][4+1];

int main(void)
{
    char word[5+1];
    int i, j, k, len, sum, diff;

    for (i = 1; i <= 26; i++) {
        C[i][0] = 0;
        C[i][1] = i;
    }

    for (i = 1; i <= 26; i++)
        for (j = 2; j <= i && j <= 4; j++)
            C[i][j] = C[i][j-1] * (i-j+1) / j;

    while (gets(word) != NULL) {
        len = strlen(word);

        /* If the length is 1, just print the integer out */
        if (len == 1) {
            printf("%d\n", word[0]-'a'+1);
            continue;
        }

        /* If the word is not strictly increasing, print 0 */
        for (i = 1; i < len; i++)
            if (word[i-1] >= word[i])
                break;
        if (i != len) {
            printf("0\n");
            continue;
        }

        sum = 0;
        /* length = 1 ~ len-1 */
        for (i = 1; i < len; i++)
            sum += C[26][i];
        /* first letter */
        for (i = 25, diff = word[0] - 'a'; i >= 26-diff; i--)
            sum += C[i][len-1];
        /* middle letters */
        for (i = 1; i < len-1; i++)
            for (k = 1, j = 24 - (word[i-1] - 'a'); k <= (word[i]-word[i-1]-1); k++, j--)
                sum += C[j][len-i-1];
        /* last letter */
        sum += C[word[len-1]-word[len-2]][1];
        printf("%d\n", sum);
    }

    return 0;
}