Leetcode 3337. Total Characters in String After Transformations II

• Leetcode 3337. Total Characters in String After Transformations II
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3337. Total Characters in String After Transformations II

1. 解题思路

这一题是这次最有意思的一道题目，可惜我也没有自力搞定，看了题目才恍然大悟的……

这一题就是一道纯·数学问题，我们可以给定的变化用一个转移矩阵进行表示：

$$T=\left[\begin{array}{ccccc}{t}_{aa}& t_{ab}& t_{ac}& \cdots & t_{az}\\ t_{ba}& t_{bb}& t_{bc}& \cdots & t_{bz}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ t_{za}& t_{zb}& t_{zc}& \cdots & t_{zz}\end{array}\right]$$

其中，$t_{ij}$表示字符$i$经过一次变换之后产生的字符$j$的个数。

我们使用数组$a=(n_a,n_b,n_c,\cdots ,n_z)$表示原始字符串当中字符$a$到$z$各自出现的次数，那么，不难写出，经过$t$次操作之后最终得到的字符串当中各个字符的个数即为：

$$o=a\cdot T^t$$

因此，这就变成一个矩阵连乘的问题了，和一般的n次方问题完全一样了，直接二分求解即可。

2. 代码实现

给出python代码实现如下：

MOD = 10**9+7class Solution:def lengthAfterTransformations(self, s: str, t: int, nums: List[int]) -> int:def mat_mul(A, B):assert(len(A[0]) == len(B))n, m, l = len(A), len(A[0]), len(B[0])out = [[0 for _ in range(l)] for _ in range(n)]for i in range(n):for j in range(l):for k in range(m):out[i][j] = (out[i][j] + A[i][k] * B[k][j]) % MODreturn outmat = [[0 for _ in range(26)] for _ in range(26)]for i, j in enumerate(nums):for k in range(1, j+1):mat[i][(i+k) % 26] = 1@lru_cache(None)def mat_pow(n):if n == 1:return matreturn mat_mul(mat_pow(n//2), mat_pow(n-n//2))mat = mat_pow(t)cnt = [0 for _ in range(26)]for ch in s:cnt[ord(ch) - ord('a')] += 1out = [0 for _ in range(26)]for j in range(26):for i in range(26):out[j] = (out[j] + cnt[i] * mat[i][j]) % MODreturn sum(out) % MOD

提交代码评测得到：耗时3719ms，占用内存25.3MB。