设$dp[i][j]$为$s_1$~$s_i$经过操作得到以'a'+j为结尾的字符串的方案数.

那么转移方程就是枚举上一个字符$j$, 而后枚举上一个字符经过操作后的偏移量$d$, 那么当前位置的新字符就为s[i] + d, 则dp[i][s[i]+d-'a']+=dp[i-1][j]即可, 但是无法通过样例, 因此想问一下这个思路是否可行? 感谢!

代码如下:

#include <bits/stdc++.h>

#define debug() freopen("../test.in", "r", stdin)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define abs(x) ((x) >= 0 ? (x) : -(x))
#define mst(x, y) memset((x), (y), sizeof (x))
#define endl '\n'

using namespace std;

__attribute__((unused)) typedef long long ll;
__attribute__((unused)) typedef unsigned long long ull;
__attribute__((unused)) typedef pair<int, int> pii;

__attribute__((unused)) inline ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' and ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

__attribute__((unused)) const double Pi = 3.1415926535897932384626433832795;
__attribute__((unused)) const int maxN = 1e4 + 5, maxM = 1e2 + 5, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

string s;
int n;

ll dp[maxN][30] = {};

int main() {
    int T = read();
    while (T--) {
        cin >> s;
        s.insert(s.begin(), 1, ' ');
        mst(dp, 0);
        dp[1][s[1] - 'a'] = 1;
        n = s.size() - 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 0; j < 26; ++j) {
                dp[i][s[i] - 'a'] = (dp[i][s[i] - 'a'] + dp[i - 1][j]) % MOD;
            }
            for (int j = 0; j < 26; ++j) {
                if (not dp[i - 1][j])
                    continue;
                for (int k = j - 1; k >= 0; --k) {
                    int delta = j - k, nxt = s[i] + delta;
                    if (nxt > 'z')
                        break;
                    dp[i][nxt - 'a'] = (dp[i][nxt - 'a'] + dp[i - 1][j]) % MOD;
                }
                for (int k = j + 1; k < 26; ++k) {
                    int delta = k - j, nxt = s[i] - delta;
                    if (nxt < 'a')
                        break;
                    dp[i][nxt - 'a'] = (dp[i][nxt - 'a'] + dp[i - 1][j]) % MOD;
                }
            }
        }
        ll ans = 0;
        for (int i = 0; i < 26; ++i) {
            ans = (ans + dp[n][i]) % MOD;
        }
        cout << (ans - 1 + MOD) % MOD << endl;
    }
}