3337. Total Characters in String After Transformations II
https://leetcode.com/problems/total-characters-in-string-after-transformations
-ii
昨天的題目 前天的進階版
這次輸入多了一個26長度矩陣
代表每次迭代26個字母分別要分裂次
分裂的在下一次迭代還會繼續分裂
數字會越來越多 很可怕
其他輸入則一樣 一個初始字串 跟 迭代次數
思路：
要用矩陣運算來做 本質數學題
在題目看到要你 mod 10^9+7
通常代表不能暴力破解/遞迴memo
因為計算量太大了
Code:
題目比較複雜我就分段寫
這題要做幾個步驟
1. 初始化字母的頻率
2. 建立轉移矩陣
3. 矩陣快速冪
4. 計算 M^t × v0
5. 計算總和
1. 初始化字母頻率
const ALPHABET: usize = 26;
const MOD: u64 = 1_000_000_007;
let mut freq = [0u64; ALPHABET];
for c in s.chars() {
freq[(c as u8 - b'a') as usize] += 1;
}
2. 建立轉移矩陣
let mut matrix = [[0u64; ALPHABET]; ALPHABET];
for i in 0..ALPHABET {
for k in 1..=nums[i] as usize {
let j = (i + k) % ALPHABET;
matrix[j][i] += 1;
}
}
這個轉移矩陣的目的是
讓每次計算後得知每次每個母體會分裂出幾個新字母
matrix[j][i] 代表：一個字母 i 會貢獻出幾個字母 j
ex.
nums['a'] = 3 → 'a' → 'b','c','d' // a 在 nums['a'] = 3 會分裂三個字母
結果就是：M[1][0] += 1, M[2][0] += 1, M[3][0] += 1
3. 矩陣快速冪
let mut result = [[0u64; ALPHABET]; ALPHABET];
for i in 0..ALPHABET {
result[i][i] = 1;
}
let mut base = matrix;
let mut exp = t as u64;
while exp > 0 {
if exp % 2 == 1 {
result = Self::multiply_matrices(&result, &base, MOD);
}
base = Self::multiply_matrices(&base, &base, MOD);
exp /= 2;
}
多次轉換 = 連續乘法
因為每一次轉換都像這樣：
v1 = M × v0
v2 = M × v1 = M^2 × v0
v3 = M × v2 = M^3 × v0
...
vt = Mt × v0 = M^t × v0
觀察規則
最終可以得到
v_final = M^t × v0
答案就是
sum(v_final) % MOD
所以得到第四步跟第五步
4. M^t × v0
let mut final_freq = [0u64; ALPHABET];
for i in 0..ALPHABET {
for j in 0..ALPHABET {
final_freq[i] = (final_freq[i] + result[i][j] * freq[j] % MOD)
% MOD;
}
}
5. 算出總和 sum(v_final) % MOD
(final_freq.iter().sum::<u64>() % MOD) as i32
就是答案
Final Code:
impl Solution {
pub fn length_after_transformations(s: String, t: i32, nums: Vec<i32>)
-> i32 {
const ALPHABET: usize = 26;
const MOD: u64 = 1_000_000_007;
// 1. 初始字母頻率
let mut freq = [0u64; ALPHABET];
for c in s.chars() {
freq[(c as u8 - b'a') as usize] += 1;
}
// 2. 建立轉移矩陣
let mut matrix = [[0u64; ALPHABET]; ALPHABET];
for i in 0..ALPHABET {
for k in 1..=nums[i] as usize {
let j = (i + k) % ALPHABET;
matrix[j][i] += 1;
}
}
// 3. 矩陣快速冪
let mut result = [[0u64; ALPHABET]; ALPHABET];
for i in 0..ALPHABET {
result[i][i] = 1;
}
let mut base = matrix;
let mut exp = t as u64;
while exp > 0 {
if exp % 2 == 1 {
result = Self::multiply_matrices(&result, &base, MOD);
}
base = Self::multiply_matrices(&base, &base, MOD);
exp /= 2;
}
// 4. M^t × v
let mut final_freq = [0u64; ALPHABET];
for i in 0..ALPHABET {
for j in 0..ALPHABET {
final_freq[i] = (final_freq[i] + result[i][j] * freq[j] % MOD)
% MOD;
}
}
// 5. 總和
(final_freq.iter().sum::<u64>() % MOD) as i32
}
// 矩陣 multiply
fn multiply_matrices(a: &[[u64; 26]; 26], b: &[[u64; 26]; 26], modulo: u64)
-> [[u64; 26]; 26] {
let mut res = [[0u64; 26]; 26];
for i in 0..26 {
for j in 0..26 {
for k in 0..26 {
res[i][j] = (res[i][j] + a[i][k] * b[k][j] % modulo)
% modulo;
}
}
}
res
}
}