问题描述

给定一个由小写英文字母组成的字符串 s、一个整数 t（转换次数）以及一个长度为 26 的数组 nums。每次转换时，字符串中的每个字符 s[i] 都会替换为字母表中它后面连续的 nums[s[i] - 'a'] 个字符，如果超出 'z' 则回绕到字母表开头。

例如，'a' 且 nums[0] = 3，则 'a' 转换为 "bcd"；'y' 且 nums[24] = 3，则 'y' 转换为 "zab"。要求返回恰好执行 t 次转换后字符串的长度，结果对 10^9 + 7 取模。

算法思路

核心思想：使用矩阵快速幂优化转换过程。

1. 状态表示：用一个长度为 26 的向量 count 表示当前每种字符的出现次数。
2. 构建转移矩阵：构建一个 26 x 26 的矩阵 M，其中 M[i][j] = 1 表示字符 i 经过一次转换会产生一个字符 j。
3. 计算转移矩阵的 t 次幂：利用快速幂计算 M^t。
4. 计算最终状态：将初始计数向量与 M^t 相乘，得到最终每种字符的计数。
5. 求和：将最终计数向量的所有元素相加，得到最终字符串长度。

Rust 实现

```rust
const MOD: i64 = 1_000_000_007;
const SIZE: usize = 26;

impl Solution {
    pub fn length_after_transformations(s: String, t: i32, nums: Vec<i32>) -> i32 {
        let t = t as usize;

        // 1. 统计初始字符串中每个字符的出现次数
        let mut count = vec![0i64; SIZE];
        for ch in s.chars() {
            count[(ch as u8 - b'a') as usize] += 1;
        }

        // 2. 构建转移矩阵
        let mut matrix = vec![vec![0i64; SIZE]; SIZE];
        for i in 0..SIZE {
            let num = nums[i] as usize;
            for j in 1..=num {
                let idx = (i + j) % SIZE;
                matrix[i][idx] = 1;
            }
        }

        // 3. 计算转移矩阵的 t 次幂
        let power = Self::matrix_pow(&matrix, t);

        // 4. 计算最终计数向量: count * power
        let mut final_count = vec![0i64; SIZE];
        for i in 0..SIZE {
            for j in 0..SIZE {
                final_count[i] = (final_count[i] + count[j] * power[j][i]) % MOD;
            }
        }

        // 5. 求和得到最终长度
        let mut ans = 0;
        for &val in &final_count {
            ans = (ans + val) % MOD;
        }
        ans as i32
    }

    // 矩阵乘法
    fn matrix_mul(a: &Vec<Vec<i64>>, b: &Vec<Vec<i64>>) -> Vec<Vec<i64>> {
        let n = a.len();
        let mut res = vec![vec![0i64; n]; n];
        for i in 0..n {
            for k in 0..n {
                if a[i][k] == 0 {
                    continue;
                }
                let aik = a[i][k];
                for j in 0..n {
                    res[i][j] = (res[i][j] + aik * b[k][j]) % MOD;
                }
            }
        }
        res
    }

    // 矩阵快速幂
    fn matrix_pow(mat: &Vec<Vec<i64>>, mut exp: usize) -> Vec<Vec<i64>> {
        let n = mat.len();
        // 初始化为单位矩阵
        let mut res = vec![vec![0i64; n]; n];
        for i in 0..n {
            res[i][i] = 1;
        }

        let mut base = mat.clone();
        while exp > 0 {
            if exp & 1 == 1 {
                res = Self::matrix_mul(&res, &base);
            }
            base = Self::matrix_mul(&base, &base);
            exp >>= 1;
        }
        res
    }
}
```

代码说明

· matrix_mul：优化了矩阵乘法，跳过零元素以提高效率。
· matrix_pow：实现了二进制快速幂，将 O(t) 的转换次数优化为 O(log t)。
· 向量与矩阵相乘：注意乘法顺序，最终计数向量 = 初始计数向量 × M^t。

复杂度分析

· 时间复杂度：O(SIZE^3 * log t)，其中 SIZE = 26 是常数，因此实际为 O(log t)。
· 空间复杂度：O(SIZE^2)，用于存储矩阵。