密令
题目描述
给定一小写字母串 \(s\)，每次操作你可以选择一个 \(p\)（\(1 \leq p \lt |s|\)）执行下述修改中的任意一个：
- 将 \(s_p\) 改为其字典序 \(+1\) 的字母，将 \(s_{p+1}\) 改为其字典序 \(-1\) 的字母；
- 将 \(s_p\) 改为其字典序 \(-1\) 的字母，将 \(s_{p+1}\) 改为其字典序 \(+1\) 的字母。
在经过任意多次操作后，串 \(s\) 能变化成多少种字符串？
修改过程中必须保证 \(s\) 是合法的小写字母串（即不能对字母 a 进行字典序 \(-1\) 的操作），答案对 \(10^9 + 7\) 取模。
输入格式
第一行一个整数 \(T\)，表示数据组数
接下来 \(T\) 行，每行一个小写字母串 \(s\)。
输出格式
输出 \(T\) 行，每行一个整数表示答案。
样例 #1
样例输入 #1
3
aaaaaaaaa
ya
klmbfxzb
样例输出 #1
0
24
320092793
提示
- 对于 \(30\%\) 的数据，\(T=1,|s| \leq 10\)；
- 对于 \(60\%\) 的数据，\(T \leq 10\)；
- 对于 \(100\%\) 的数据，\(T \leq 10000,1 \leq |s| \leq 100\)。
思路
显然我们可以知道的是这两个操作可以使每个位置随意转移
所以我们只维护一维总和 显然还要维护的一维是个数 cnt肯定是与个数有关的
但是这样我们的状态数就是2600*100 如果再乘上T 肯定会超时
那我们发现这个状态设计其实是涵盖了所有情况的 我们只需要算一次
然后O（1）查询即可
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
const int M = 998244353;
const int mod = 1e9+7;
#define int long long
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int dp[110][2610];
void solve() {
string s;cin>>s;
int cnt=0;
for(int i=0;i<s.size();i++)cnt+=s[i]-'a';
cout<<(dp[s.size()][cnt]-1)%mod<<endl;
}
signed main(){
fast
int T;cin>>T;
for(int i=0;i<26;i++)dp[1][i]=1;
for(int i=2;i<=100;i++) {
dp[i][0] = 1;
for (int j = 1; j <= 2600; j++)
for (int k = 0; k < 26; k++)
if (j - k >= 0)(dp[i][j] += dp[i - 1][j - k]) %= mod;
}
while(T--) {
solve();
}
return ~~(0^_^0);
}