P1385 密令题解

思路

我们发现两种操作都不会影响字符之和。

考虑动态规划，

设 \(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;
}