Codeforces 156 C. Cipher

問題

英小文字からなる文字列sが与えられる。
sの任意の連続する二文字に対して、1文字目をアルファベット順で一つ進めて、2文字目を一つ戻す、
または1文字目を一つ戻して、2文字目を一つ進める、
という操作が何度でも行える。

ただし、aの前の文字は存在せず、zの後の文字は存在しないものとする。

sから操作を0回以上繰り返して得られる文字列は（s以外に）いくつあるか、求めよ。

制約条件

文字列の長さ≦100
文字列の個数≦10^4

方針

文字列の各桁の和は、操作仕方によらず、一定である。
また、各桁の和が一定の文字列は、操作によって全て互いに変形することができる。

したがって、長さi文字で、各桁の和がjであるような文字列の個数をdp[i][j]とし、
これを更新するような動的計画法をあらかじめしておけば、
各桁の和と長さから、変形できる文字列の個数が求まることになる。

ソースコード

const int mod = (int)1e9 + 7;
int t;
int dp[110][110*26];

void run()
{
	dp[0][0]=1;
	rep(i,105)rep(j,(i+1)*26)if(dp[i][j])rep(k,26)(dp[i+1][j+k]+=dp[i][j])%=mod;
	
	cin>>t;
	rep(i,t){
		int a=0;
		string s;
		cin>>s;
		rep(j,s.size())a+=s[j]-'a';
		cout<<(dp[s.size()][a]+mod-1)%mod<<endl;
	}
}