|
|
思路：
f[ch][len] = { 有多少個(gè)以 ch 開頭，長(zhǎng)度為 len 的字符串 }
 #include <stdio.h>
__int64 dp[16][32], sum[16], ans;
int main()
   {
 int i, j, len;
char str[16];
freopen("e:\\test\\in.txt", "r", stdin);
for (i = 0; i < 26; i++)
dp[0][i] = 1;
  for (i = 1; i < 10; i++) {
for (j = 25 - i; j >= 0; j--) {
dp[i][j] += dp[i][j + 1];
dp[i][j] += dp[i - 1][j + 1];
 }
}
for (i = 0; i < 10; i++)
for (j = 0; j < 26; j++)
sum[i] += dp[i][j];
scanf("%s", str);
for (len = 0; str[len]; len++)
ans += sum[len];
ans -= sum[len - 1];
j = 0;
for (i = len - 1; i >= 0; i--) {
while (j < str[len - 1 - i] - 'a') {
ans += dp[i][j];
j++;
}
j++;
}
for (i = 0; i < len - 1; i++)
if (str[i] >= str[i + 1])
ans = -1;
printf("%I64d\n", ans + 1);
return 0;
 }
|