POJ 1850

一道比较复杂的模拟题
一步步从字母的最前方计算到最后方即可
 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 using namespace std;
 5 #define ll long long
 6 
 7 ll sum[10];
 8 char s[12];
 9 
10 void init()
11 {
12     for(int i=1 ; i<=9 ; i++){
13         ll tmp = 1;
14         for(int j=26 ; j>26-i ; j--)
15             tmp *= j;
16         for(int j=1 ; j<=i ;j++)
17             tmp /= j;
18         sum[i] = sum[i-1] + tmp;
19     }
20 }
21 
22 bool ok(int len)
23 {
24     for(int i=1 ; i<len ; i++){
25         if(s[i] - s[i-1] <= 0) return false;
26     }
27     return true;
28 }
29 
30 ll C(int n , int m)
31 {
32     ll ans = 1;
33     for(int i=n ; i>n-m ; i--)
34         ans *= i;
35     for(int i=1 ; i<=m ; i++)
36         ans /= i;
37     return ans;
38 }
39 
40 int main()
41 {
42   //  freopen("a.in" , "r" , stdin);
43     init();
44     while(scanf("%s" , s) != EOF)
45     {
46         int len = strlen(s);
47 
48         if(!ok(len)){
49             puts("0");
50             continue;
51         }
52 
53         ll ans = sum[len-1];
54         for(int i=0 ; i<len ; i++){
55             if(i == 0){
56                 for(int j=1 ; j<(int)(s[i]-'a'+1) ; j++){
57                     ans += C(26-j , len-1-i);
58                 }
59             }
60             else{
61                 for(int j=(int)(s[i-1]-'a'+2) ; j<(int)(s[i]-'a'+1) ; j++){
62                     ans += C(26-j , len-1-i);
63                 }
64             }
65         }
66         ans ++;
67         printf("%I64d
" , ans);
68     }
69     return 0;
70 }