企业官网建设流程全解析

这道题可以使用矩阵快速幂来高效解决。因为转换次数ttt最大可以达到10910^9109，如果直接模拟每次转换会导致超时，而通过构建状态转移矩阵并使用快速幂，可以把时间复杂度从O(t×26)O(t \times 26)O(t×26)降至O(log⁡t×263)O(\log t \times 26^3)O(logt×263)。
解题思路
状态表示：
我们可以用一个长度为 26 的一维数组（向量）来记录当前字符串中各个字母的数量。
状态转移矩阵：
根据题目给定的 nums 数组，字母 c 在一次转换后会变成它后面的 nums[c] 个字母（循环字母表）。例如，如果 nums[0] = 2，则 ‘a’ 会变成 ‘b’ 和 ‘c’。
我们可以据此构造一个26×2626 \times 2626×26的矩阵MMM，其中 M[i][j] 表示字母 i 经过一次转换后会生成多少个字母 j。
矩阵快速幂：
经过ttt次转换后的转移矩阵即为MtM^tMt。用初始状态向量乘以MtM^tMt，就能得到ttt次转换后各个字母的数量。
大数处理：
由于 JavaScript 中的普通 Number 类型最大安全整数约为9×10159 \times 10^{15}9×1015，而两个取模后的数相乘可能会超过这个值导致精度丢失，因此我们需要使用 BigInt 来进行矩阵运算，最后再转换回普通数字。
JavaScript 实现
/**

• @param {string} s
• @param {number} t
• @param {number[]} nums
• @return {number}
  */
  var lengthAfterTransformations = function(s, t, nums) {
  const MOD = 1000000007n;
  const size = 26;
  // 1. 初始化状态向量 v，记录初始字符串中每个字母的数量
  let v = new Array(size).fill(0n);
  for (const c of s) {
  v[c.charCodeAt(0) - 97]++;
  }
  // 2. 构造状态转移矩阵 M
  let M = Array.from({ length: size }, () => new Array(size).fill(0n));
  for (let i = 0; i < size; i++) {
  for (let j = 1; j <= nums[i]; j++) {
  M[i][(i + j) % size] = 1n;
  }
  }
  // 矩阵乘法函数
  function multiply(A, B) {
  let C = Array.from({ length: size }, () => new Array(size).fill(0n));
  for (let i = 0; i < size; i++) {
  for (let k = 0; k < size; k++) {
  if (A[i][k] === 0n) continue;
  for (let j = 0; j < size; j++) {
  C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
  }
  }
  }
  return C;
  }
  // 矩阵快速幂函数
  function matPow(mat, p) {
  // 初始化为单位矩阵
  let res = Array.from({ length: size }, () => new Array(size).fill(0n));
  for (let i = 0; i < size; i++) {
  res[i][i] = 1n;
  }
  while (p > 0n) {
  if (p & 1n) {
  res = multiply(res, mat);
  }
  mat = multiply(mat, mat);
  p >>= 1n;
  }
  return res;
  }
  // 3. 计算 M^t
  let Mt = matPow(M, BigInt(t));
  // 4. 计算最终的字母数量向量：v * M^t
  let finalV = new Array(size).fill(0n);
  for (let i = 0; i < size; i++) {
  for (let j = 0; j < size; j++) {
  finalV[j] = (finalV[j] + v[i] * Mt[i][j]) % MOD;
  }
  }
  // 5. 汇总所有字母的数量，即为最终字符串的长度
  let ans = 0n;
  for (let i = 0; i < size; i++) {
  ans = (ans + finalV[i]) % MOD;
  }
  return Number(ans);
  };