容易发现,如果把字母表映射到 \([1,26]\) 上,那么无论怎么操作总和都不变。
于是可已将问题转化为:有多少种长度为 \(n\) 的序列,满足每个元素在 \([1,26]\) 之间,总和为 \(sum\)。
定义 \(f_{i,j}\) 表示处理到第 \(i\) 个元素,总和为 \(j\) 的合法方案数。
转移方程为 \(f_{i,j}=\sum\limits_{k=1}^{26}f_{i-1,j-k}\),其中 \(f_{0,0}=1\)。
复杂度 \(O(n^226^2)\)。
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100+5,mod=1e9+7;
ll T,f[N][27*N];
string s;
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>T;
f[0][0]=1;
for(int i=1;i<=100;++i){
for(int j=1;j<=2600;++j){
for(int k=1;k<=min(26,j);++k){
f[i][j]=(f[i][j]+f[i-1][j-k])%mod;
}
}
}
while(T--){
cin>>s;
ll sum=0,len=s.size();for(int i=0;i<len;++i)sum+=s[i]-'a'+1;
cout<<f[len][sum]-1<<endl;
}
return 0;
}