2025-05-26：字符串转换后的长度Ⅱ。用go语言，你有一个只包含小写字母的字符串 s，一个整数 t 表示转换次数，还有一个长度为 26 的数组 nums。每次转换过程如下：

• 对字符串 s 中的每个字符 s[i]，用字母表中紧跟该字母后面连续的 nums[s[i]-‘a’] 个字符替换它。

• 超过字母表 ‘z’ 的部分，会从字母表开头重新开始计数（即循环回绕）。

例如，字符 ‘a’ 且对应 nums[0] = 3，则它被替换成 ‘b’、‘c’、‘d’ 三个字母。如果字符是 ‘y’ 且 nums[24] = 3，则替换成 ‘z’、‘a’、‘b’。

经过 t 次这样的转换后，返回最终字符串的长度（结果对 1000000007 取模）。

1 <= s.length <= 100000。

s 仅由小写英文字母组成。

1 <= t <= 1000000000。

nums.length == 26。

1 <= nums[i] <= 25。

输入： 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 个字符。

题目来自力扣3337。

解题思路

直接模拟每次转换的过程是不可行的，因为 t 可以达到 1e9，而字符串长度可以达到 1e5，时间复杂度会爆炸（O(t * len(s))）。

矩阵快速幂优化：

观察到每次转换中，每个字符的替换是独立的，且替换后的字符数量取决于当前字符和 nums 数组。我们可以用矩阵乘法来表示字符的转换关系：

• 定义一个 26x26 的转移矩阵 T，其中 T[i][j] 表示字符 j 在转换后对字符 i 的贡献（即字符 j 会被替换为多少个字符 i）。
  • 对于字符 j，它会替换为 nums[j] 个连续字符，分别是 (j+1)%26, (j+2)%26, …, (j+nums[j])%26。
  • 因此，T[(j+k)%26][j] = 1，其中 k 从 1 到 nums[j]。
• 初始时，统计字符串 s 中每个字符的频率 f（f[i] 表示字符 'a'+i 的出现次数）。
• 经过 t 次转换后，字符的频率向量 f_t 可以通过矩阵快速幂计算：f_t = T^t * f。
• 最终字符串的长度是 f_t 中所有元素的和。

具体步骤：

1. 构建转移矩阵 T：
   • 对于每个字符 j（0 到 25），遍历 k 从 1 到 nums[j]，设置 T[(j+k)%26][j] = 1。
   • 这样，T[i][j] 表示字符 j 在转换后会贡献多少个字符 i。
2. 初始频率 f：
   • 统计 s 中每个字符的出现次数。
3. 计算 T^t：
   • 使用矩阵快速幂高效计算 T 的 t 次幂。
4. 计算 f_t = T^t * f：
   • 矩阵乘法计算新的频率向量。
5. 求和：
   • f_t 中所有元素的和就是最终字符串的长度。

时间复杂度和空间复杂度

• 时间复杂度：
  • 构建转移矩阵 T：O(26 * max(nums)) ≈ O(26 * 25) = O(650)。
  • 矩阵快速幂：每次矩阵乘法是 O(26^3) = O(17576)，共 O(log t) 次，因此是 O(17576 * log t)。
  • 计算 f_t：矩阵乘向量是 O(26^2) = O(676)。
  • 总时间复杂度：O(650 + 17576 * log t + 676) ≈ O(log t)（因为 26^3 是常数）。
• 空间复杂度：
  • 转移矩阵 T 和中间矩阵：O(26^2) = O(676)。
  • 频率向量：O(26)。
  • 总空间复杂度：O(1)（常数空间，与输入规模无关）。

总结

通过矩阵快速幂，我们将问题从 O(t * len(s)) 优化到 O(log t) 的时间复杂度，能够高效处理 t 很大的情况。空间复杂度是常数 O(1)。

Go完整代码如下：

package main

import (
	"fmt"
)

const MOD = 1e9 + 7
const L = 26

func lengthAfterTransformations(s string, t int, nums []int) int {
	T := NewMat()
	for i := 0; i < L; i++ {
		for j := 1; j <= nums[i]; j++ {
			T.a[(i+j)%L][i] = 1
		}
	}

	res := quickMul(T, t)
	f := make([]int, L)
	for _, ch := range s {
		f[ch-'a']++
	}

	ans := 0
	for i := 0; i < L; i++ {
		for j := 0; j < L; j++ {
			ans = (ans + res.a[i][j]*f[j]) % MOD
		}
	}
	return ans
}

type Mat struct {
	a [L][L]int
}

func NewMat() *Mat {
	return &Mat{}
}

func NewMatCopy(from *Mat) *Mat {
	m := &Mat{}
	for i := 0; i < L; i++ {
		for j := 0; j < L; j++ {
			m.a[i][j] = from.a[i][j]
		}
	}
	return m
}

func (m *Mat) Mul(other *Mat) *Mat {
	result := NewMat()
	for i := 0; i < L; i++ {
		for j := 0; j < L; j++ {
			for k := 0; k < L; k++ {
				result.a[i][j] = (result.a[i][j] + m.a[i][k]*other.a[k][j]) % MOD
			}
		}
	}
	return result
}

/* 单位矩阵 */
func I() *Mat {
	m := NewMat()
	for i := 0; i < L; i++ {
		m.a[i][i] = 1
	}
	return m
}

/* 矩阵快速幂 */
func quickMul(x *Mat, y int) *Mat {
	ans := I()
	cur := NewMatCopy(x)
	for y > 0 {
		if y&1 == 1 {
			ans = ans.Mul(cur)
		}
		cur = cur.Mul(cur)
		y >>= 1
	}
	return ans
}

func main() {
	s := "abcyy"
	t := 2
	nums := []int{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}
	result := lengthAfterTransformations(s, t, nums)
	fmt.Println(result)
}

Rust完整代码如下：

const MOD: i64 = 1_000_000_007;
const L: usize = 26;

type Mat = [[i64; L]; L];

fn new_mat() -> Mat {
    [[0; L]; L]
}

fn identity() -> Mat {
    let mut m = new_mat();
    for i in 0..L {
        m[i][i] = 1;
    }
    m
}

fn mat_mul(a: &Mat, b: &Mat) -> Mat {
    let mut res = new_mat();
    for i in 0..L {
        for j in 0..L {
            let mut sum = 0;
            for k in 0..L {
                sum += a[i][k] * b[k][j];
            }
            res[i][j] = sum % MOD;
        }
    }
    res
}

fn mat_pow(mut base: Mat, mut exp: i64) -> Mat {
    let mut result = identity();
    while exp > 0 {
        if exp & 1 == 1 {
            result = mat_mul(&result, &base);
        }
        base = mat_mul(&base, &base);
        exp >>= 1;
    }
    result
}

fn length_after_transformations(s: &str, t: i64, nums: &[i32]) -> i64 {
    // 构造转换矩阵 T，T[i][j] = 1 表示从 j 变成 i 的可能路径
    let mut T = new_mat();
    for i in 0..L {
        for j in 1..=nums[i] {
            let to = (i + j as usize) % L;
            T[to][i] = 1;
        }
    }

    // 矩阵快速幂计算 T^t
    let res = mat_pow(T, t);

    // 统计初始字符串中各字母的数量
    let mut f = [0i64; L];
    for b in s.bytes() {
        f[(b - b'a') as usize] += 1;
    }

    // 计算最终长度 = ∑_(i,j) res[i][j] * f[j]
    let mut ans = 0i64;
    for i in 0..L {
        for j in 0..L {
            ans = (ans + res[i][j] * f[j]) % MOD;
        }
    }
    ans
}

fn main() {
    let s = "abcyy";
    let t = 2;
    let 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,
    ];
    let result = length_after_transformations(s, t, &nums);
    println!("{}", result);
}