一. 题目

二. 思路

三. 代码

using LL=long long;
const int N=1e5+10, M=26, MOD=1e9+7;

int n;

class DP
{
public:
    int cnt[M];//统计字母出现次数
    LL f[N][M];
public:
    void init(string &s, int t)
    {
        n=s.size();
        fill(cnt, cnt+M, 0);
        fill(&f[0][0], &f[0][0]+N*M, 0);
        for(int i=0;i<M;++i) f[0][i]=1;//字母i变换一次
        for(int i=0;i<n;++i) ++cnt[s[i]-'a'];
    }

    int work(string &s, int t)
    {
        init(s, t);
        for(int i=1;i<=t;++i)//枚举替换i次
            for(int j=0;j<M;++j)//枚举字母
                if(j<25) f[i][j]=(f[i][j]+f[i-1][j+1])%MOD;
                else//j为'z'
                {
                    f[i][j]=(f[i][j]+f[i-1][0])%MOD;//'a'
                    f[i][j]=(f[i][j]+f[i-1][1])%MOD;//'b'
                }
        int ans=0;
        for(int j=0;j<M;++j)
            ans=(ans+1ll*cnt[j]*f[t][j])%MOD;
        return ans;
    }
}dp;

class Solution {
public:
    int lengthAfterTransformations(string s, int t) {
        return dp.work(s, t);
    }
};