思路
我们发现两种操作都不会影响字符之和。
考虑动态规划,
设 \(f_{i, j}\) 表示在前 \(i\) 位,可以达到和为 \(j\) 的方案数。
有 \(f_{i, j} = \sum\limits_{k = 0}^{25}f_{i - 1, j - k}\)。
最后记得 \(-1\),表示去除原始字符串。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2610, MOD = 1000000007;
int f[N][N];
char s[N];
int len;
int sum;
void solve() {
cin >> (s + 1);
len = strlen(s + 1);
sum = 0;
for (int i = 1; i <= len; i++) sum += s[i] - 'a';
cout << ((f[len][sum] - 1) % MOD + MOD) % MOD << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
f[0][0] = 1;
for (int i = 1; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < 26; k++) {
if (j >= k) f[i][j] = (f[i][j] + f[i - 1][j - k]) % MOD;
}
}
}
int T;
cin >> T;
while (T--) solve();
return 0;
}
标签:P1385,题解,sum,long,int,密令,MOD
From: https://www.cnblogs.com/Yuan-Jiawei/p/17660348.html