题目描述

给你一个由小写英文字母组成的字符串 s，一个整数 t 表示要执行的 转换 次数，以及一个长度为 26 的数组 nums。每次 转换 需要根据以下规则替换字符串 s 中的每个字符：

• 将 s[i] 替换为字母表中后续的 nums[s[i] - 'a'] 个连续字符。例如，如果 s[i] = 'a' 且 nums[0] = 3，则字符 'a' 转换为它后面的 3 个连续字符，结果为 "bcd"。
• 如果转换超过了 'z'，则 回绕 到字母表的开头。例如，如果 s[i] = 'y' 且 nums[24] = 3，则字符 'y' 转换为它后面的 3 个连续字符，结果为 "zab"。

返回 恰好 执行 t 次转换后得到的字符串的 长度。

由于答案可能非常大，返回其对 10^9 + 7 取余的结果。

样例

输入： s = "abcyy", t = 2, nums = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2]

输出： 7

解释：

第一次转换 (t = 1)

'a' 变为 'b' 因为 nums[0] == 1
'b' 变为 'c' 因为 nums[1] == 1
'c' 变为 'd' 因为 nums[2] == 1
'y' 变为 'z' 因为 nums[24] == 1
'y' 变为 'z' 因为 nums[24] == 1
第一次转换后的字符串为: "bcdzz"
第二次转换 (t = 2)

'b' 变为 'c' 因为 nums[1] == 1
'c' 变为 'd' 因为 nums[2] == 1
'd' 变为 'e' 因为 nums[3] == 1
'z' 变为 'ab' 因为 nums[25] == 2
'z' 变为 'ab' 因为 nums[25] == 2
第二次转换后的字符串为: "cdeabab"
字符串最终长度： 字符串为 "cdeabab"，长度为 7 个字符。

输入： s = "azbk", t = 1, nums = [2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]

输出： 8

解释：

第一次转换 (t = 1)

'a' 变为 'bc' 因为 nums[0] == 2
'z' 变为 'ab' 因为 nums[25] == 2
'b' 变为 'cd' 因为 nums[1] == 2
'k' 变为 'lm' 因为 nums[10] == 2
第一次转换后的字符串为: "bcabcdlm"
字符串最终长度： 字符串为 "bcabcdlm"，长度为 8 个字符。

限制

• 1 <= s.length <= 10^5
• s 仅由小写英文字母组成。
• 1 <= t <= 10^9
• nums.length == 26
• 1 <= nums[i] <= 25

算法

(矩阵快速幂) $O(n + |\Sigma|^3 \log t)$

1. 注意到，如果把字符的出现次数看成一个列向量，则每次操作都可以看成一个矩阵乘上这个列向量，得到一个新的列向量。
2. 将 nums 数组根据题目规则写为一个矩阵，利用矩阵乘法的结合律，通过快速幂算出这个矩阵迭代 $t$ 次后的结果。
3. 最后将迭代 $t$ 次的矩阵乘上这个列向量，得到最终每个字符的出现次数，求和就是答案。

时间复杂度

• 预处理列向量的时间复杂度为 $O(n)$。
• 单次矩阵乘法的时间复杂度为 $O(|\Sigma|^3)$。
• 快速幂操作 $\log t$ 次。
• 故总时间复杂度为 $O(n + |\Sigma|^3 \log t)$。

空间复杂度

• 需要 $O(|\Sigma|^2)$ 的额外空间存储矩阵和列向量。

C++ 代码

#define LL long long

const int N = 26;
const int mod = 1000000007;

struct M {
    int a[N][N];
    M() {
        memset(a, 0, sizeof(a));
    }

    void init() {
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                a[i][j] = i == j;
    }
};

M operator * (const M &x, const M &y) {
    M z;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            for (int k = 0; k < N; k++)
                z.a[i][j] = (z.a[i][j] + (LL)(x.a[i][k]) * y.a[k][j]) % mod;

    return z;
}

class Solution {
private:
    M power(M x, int y) {
        M res, p = x;
        res.init();

        for (; y; y >>= 1) {
            if (y & 1)
                res = res * p;
            p = p * p;
        }

        return res;
    }

public:
    int lengthAfterTransformations(string s, int t, vector<int>& nums) {
        M r, m;
        for (char c : s)
            ++r.a[c - 'a'][0];

        for (int i = 0; i < N; i++)
            for (int j = i + 1; j <= i + nums[i]; j++)
                m.a[j % N][i] = 1;

        r = power(m, t) * r;

        int ans = 0;
        for (int i = 0; i < N; i++)
            ans = (ans + r.a[i][0]) % mod;

        return ans;
    }
};