Codeforces Round #110 (Div. 1) C Cipher

题目链接：Cipher

题意：有一个只含有小写字母的字符串，每次可以执行的操作有两种：1. s[i]变为字母序中前面的一个，s[i+1]变为字母序中后面的一个；2. s[i]变为字母序中后面的一个，s[i+1]变为字母序中前面的一个（'a'字母序中前一个不存在，'z'字母序中后一个不存在）。问可以编程多少种不同的字符串。

题解：把每个字母看作一个权值，每次操作权值不会发生变化，而且长度相同且权值相同的字符串是可以相互转化的。本题有多组询问，所以与处理出 dp[i][j] 表示长度为 i 的字符串权值之和为 j 的情况有多少种。对于每次询问的串，求出长度 len 和权值和 sum，答案便为 dp[len][sum]-1。其中转移方程为 dp[i][j]=dp[i-1][j-1]+dp[i-1][j-2]+......+dp[i-1][j-26]。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
LL t;
char s[105];
LL dp[105][3005];
void init(){
for(int i=1;i<=26;i++) dp[1][i]=1;
for(int i=2;i<=100;i++){
for(int j=1;j<=26*i;j++){
for(int k=1;k<=26;k++){
if(j-k>=1){
dp[i][j]=(dp[i][j]+dp[i-1][j-k])%mod;
}
}
}
}
}
int main(){
init();
scanf("%lld",&t);
while(t--){
scanf("%s",s+1);
LL len=strlen(s+1);
LL sum=0;
for(int i=1;i<=len;i++){
sum+=(s[i]-'a'+1);
}
printf("%lldn",(dp[len][sum]-1+mod)%mod);
}
return 0;
}