2025-05-26：字符串转换后的长度Ⅱ 用go语言，你有一个只包含小

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

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 取模）。

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

nums.length == 26。

输入： 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

第一次转换后的字符串为: "bcdzz"

第二次转换 (t = 2)

'd' 变为 'e' 因为 nums[3] == 1

'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)&, (j+2)&, ..., (j+nums[j])&。• 因此，T[(j+k)&][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)&][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)。

package mainimport ( "fmt")const MOD = 1e9 + 7const L = 26func lengthAfterTransformations(s string, t int, nums int)int { T := NewMat for i := 0; i 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^tlet 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);}