3335. 字符串转换后的长度 I

这个难度直接可以用dp去解决我们看

a->b

b->c

………

z->ab

那么我们用代码d[i]表示i这个字符的个数，那么从上就得出

dp[i]['a']=dp[i-1]['z'];

dp[i]['b']=dp[i-1]['a']+dp[i]['z'];

dp[i]['c']=dp[i-1]['b'];

dp[i]['z']=dp[i-1]['y];

可以看出从c-z我们都可以直接从前一个继承过来，a和b我们单独去操作即可

所以我们遍历每一步t然后对于每一步将字符串里的a-z操作就行，我们只需要知道数量，并不需要知道具体位置。

所以时间复杂度就是O(26*t)

class Solution {
public:
    int lengthAfterTransformations(string s, int t) {
        //用dp[i][j]表示操作i次后，字符j在字符串中出现的次数，
        /**
        dp[i]['a']=dp[i-1]['z'];
        dp[i]['b']=dp[i-1]['a']+dp[i]['z'];
        dp[i]['c']=dp[i-1]['b'];
        dp[i]['z']=dp[i-1]['y];
        */
        const int MOD = 1e9+7;
        vector<int> a(26,0);
        for(auto it:s)a[it-'a']++;//记录每个字符出现的次数
        for(int i=1;i<=t;i++){
            vector<int> tmp(26,0);
            for(int j=0;j<25;j++) tmp[j+1]=a[j];//继承过来b-z
            tmp[0]=a[25];//a从z继承过来
            tmp[1]=(tmp[1]+a[25])%MOD;//除了从a继承过来的还有z继承过来的
            a=tmp;
        }
        long long ans=0;
        for(int i=0;i<26;i++) ans=(ans+a[i])%MOD;
        return ans;
    }
};

难度升级：矩阵快速幂优化状压DP

分析：

首先知道初级难度的用dp去维护，我们这里也是先去找子问题，看看能不能拆解出子问题：

子问题：

假设a经过过一次，之后变成b和c。问题就变成了计算b替换(t-1)次的长度，加上，c替换(t-1)次的长度。

状态定义和状态转移：

那么我们还用dp[i][j]表示字母j替换i次的长度

上面说的例子：dp[t][0]=dp[i-1][1]+dp[i-1][2]

那么我们做推广一下：

设c=nums[i]
$$ dp[i][j]=\sum^{j+c}_{k=j+1}dp[i-1][k\%26] $$
k%26是为了z->a这个阶段

初始状态：dp[0][j]=1

最终结果$$\sum_{j=0}^{25}dp[t][j]\times a[j]$$其中a[j]是s中字母j的出现次数

这个复杂度就是解决第一题的复杂度O(26*t)

矩阵快速幂优化

如果nums=[1,1,1,1,1,1,1,1,……,1,2]就是第一题的要求，a-y都只产生一个，z产生两个。
$$ dp[i][0]=dp[i-1][1] $$

$$ dp[i][1]=dp[i-1][2] $$

$$ dp[i][25]=dp[i-1][0]+dp[i-1][1] $$

用矩阵乘法表示：
$$ \left[\begin{array}{c} dp[i][0] \\ dp[i][1] \\ dp[i][2] \\ \vdots \\ dp[i][23] \\ dp[i][24] \\ dp[i][25] \end{array}\right]=\left[\begin{array}{ccccccc} 0 & 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 0 & 1 & 0 & \cdots & 0 & 0 \\ 0 & 0 & 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & 1 & 0 \\ 0 & 0 & 0 & 0 & \cdots & 0 & 1 \\ 1 & 1 & 0 & 0 & \cdots & 0 & 0 \end{array}\right]\left[\begin{array}{c} dp[i-1][0] \\ dp[i-1][1] \\ dp[i-1][2] \\ \vdots \\ dp[i-1][23] \\ dp[i-1][24] \\ dp[i-1][25] \end{array}\right] $$
把上式中的三个矩阵记作A[i],M,A[i-1]
$$ A[i]=M\times A[i-1] $$
那么就有
$$ \begin{align} A[t] &= M \times A[i-1] \\ &= M \times M \times A[i-2] \\ & ...\\ &=M^t\times A[0] \end{align} $$
其中$M^t$ 可以用矩阵快速幂计算。$A[0]$是长为26的列向量，值全为1，对应着dp[0][j]=1

class Solution {
public:
    static const int MOD=1e9+7;
    vector<vector<int>> mul(vector<vector<int>> a,vector<vector<int>> b){
        vector<vector<int>> c(26,vector<int>(26,0));
        for(int i=0;i<26;i++){
            for(int j=0;j<26;j++){
                for(int k=0;k<26;k++){
                    c[i][j]=(c[i][j] + (long long) a[i][k]*b[k][j]%MOD)%MOD;
                }
            }
        }
        return c;
    }
    vector<vector<int>> pow(vector<vector<int>> a,int n){
        vector<vector<int>> ans(26,vector<int>(26,0));
        for(int i=0;i<26;i++){
            ans[i][i]=1;//初始为单位矩阵
        }
        while(n){
            if(n&1) ans=mul(ans,a);//矩阵相乘
            a=mul(a,a);
            n>>=1;
        }
        return ans;
    }
    int lengthAfterTransformations(string s, int t, vector<int>& nums) {
        vector<vector<int>> m(26,vector<int>(26,0));//M矩阵
        for(int i=0;i<26;i++){
            for(int j=i+1;j<=i+nums[i];j++){//这些地方是i能产生的,也就对应着M矩阵ij处为1
                m[i][j%26]=1;
            }            
        }
        m=pow(m,t);//矩阵快速幂

        vector<int> ans(26,0);//记录s字符串中有        
        for(auto it:s){
            ans[it-'a']++;
        }
        long long res=0;
        for(int i=0;i<26;i++){
            long long tmp=0;
            for(int j=0;j<26;j++){
                tmp=(tmp+m[i][j])%MOD;
            }
            res=(res+tmp*ans[i]%MOD)%MOD;
        }
        return res;

    }
};