Total Characters in String After Transformations II solution and explanation

MOD = 10**9 + 7
def total_transformed_length(s, t, nums):
    length = len(s)
    while t > 0:
        new_length = 0
        for char in s:
            char_index = ord(char) - ord('a')
            new_length += nums[char_index]
        length = new_length
        t -= 1
    return length % MOD

# Example usage
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]
print(total_transformed_length(s, t, nums))

#include <vector>
#include <string>
const int MOD = 1e9 + 7;

int totalTransformedLength(const std::string &s, int t, std::vector<int> &nums) {
    long long length = s.size();
    while (t-- > 0) {
        long long newLength = 0;
        for (char ch : s) {
            int index = ch - 'a';
            newLength += nums[index];
        }
        length = newLength;
    }
    return length % MOD;
}

// Example usage
#include <iostream>

int main() {
    std::string s = "abcyy";
    int t = 2;
    std::vector<int> 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};
    std::cout << totalTransformedLength(s, t, nums) << std::endl;
    return 0;
}

class Solution {
    private static final int MOD = 1000000007;

    public int totalTransformedLength(String s, int t, int[] nums) {
        long[] transformationLength = new long[26];
        for (int i = 0; i < 26; i++) {
            transformationLength[i] = nums[i];
        }

        long totalLength = 0;
        for (char c : s.toCharArray()) {
            int index = c - 'a';
            totalLength += transformationLength[index];
        }

        totalLength = fastPower(totalLength, t, MOD);

        return (int) (totalLength % MOD);
    }

    private long fastPower(long base, int exp, int mod) {
        long result = 1;
        while (exp > 0) {
            if (exp % 2 == 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exp /= 2;
        }
        return result;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] 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};
        System.out.println(solution.totalTransformedLength("abcyy", 2, nums));
    }
}

const MOD = 10**9 + 7;

function totalTransformedLength(s, t, nums) {
    let totalLength = 0;

    for (const char of s) {
        const index = char.charCodeAt(0) - 'a'.charCodeAt(0);
        totalLength += nums[index];
    }

    function fastPower(base, exp, mod) {
        let result = 1;
        while (exp > 0) {
            if (exp % 2 === 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exp = Math.floor(exp / 2);
        }
        return result;
    }

    return fastPower(totalLength % MOD, t, MOD);
}

// Example usage
console.log(totalTransformedLength("abcyy", 2, [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]));

function lengthAfterTransformations(s: string, t: number, nums: number[]): number {
    const MOD = BigInt(1e9 + 7);
    const M = 26;

    const cnt: number[] = Array(M).fill(0);
    for (const c of s) {
        cnt[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }

    const matrix: number[][] = Array.from({ length: M }, () => Array(M).fill(0));
    for (let i = 0; i < M; i++) {
        for (let j = 1; j <= nums[i]; j++) {
            matrix[i][(i + j) % M] = 1;
        }
    }

    const matmul = (a: number[][], b: number[][]): number[][] => {
        const n = a.length,
            p = b.length,
            q = b[0].length;
        const res: number[][] = Array.from({ length: n }, () => Array(q).fill(0));
        for (let i = 0; i < n; i++) {
            for (let k = 0; k < p; k++) {
                const aik = BigInt(a[i][k]);
                if (aik !== BigInt(0)) {
                    for (let j = 0; j < q; j++) {
                        const product = aik * BigInt(b[k][j]);
                        const sum = BigInt(res[i][j]) + product;
                        res[i][j] = Number(sum % MOD);
                    }
                }
            }
        }
        return res;
    };

    const matpow = (mat: number[][], power: number): number[][] => {
        let res: number[][] = Array.from({ length: M }, (_, i) =>
            Array.from({ length: M }, (_, j) => (i === j ? 1 : 0)),
        );
        while (power > 0) {
            if (power % 2 === 1) res = matmul(res, mat);
            mat = matmul(mat, mat);
            power = Math.floor(power / 2);
        }
        return res;
    };

    const cntMat: number[][] = [cnt.slice()];
    const factor = matpow(matrix, t);
    const result = matmul(cntMat, factor);

    let ans = 0n;
    for (const v of result[0]) {
        ans = (ans + BigInt(v)) % MOD;
    }
    return Number(ans);
}

func lengthAfterTransformations(s string, t int, nums []int) int {
	const MOD = 1e9 + 7
	const M = 26

	cnt := make([]int, M)
	for _, c := range s {
		cnt[int(c-'a')]++
	}

	matrix := make([][]int, M)
	for i := 0; i < M; i++ {
		matrix[i] = make([]int, M)
		for j := 1; j <= nums[i]; j++ {
			matrix[i][(i+j)%M] = 1
		}
	}

	matmul := func(a, b [][]int) [][]int {
		n, p, q := len(a), len(b), len(b[0])
		res := make([][]int, n)
		for i := 0; i < n; i++ {
			res[i] = make([]int, q)
			for k := 0; k < p; k++ {
				if a[i][k] != 0 {
					for j := 0; j < q; j++ {
						res[i][j] = (res[i][j] + a[i][k]*b[k][j]%MOD) % MOD
					}
				}
			}
		}
		return res
	}

	matpow := func(mat [][]int, power int) [][]int {
		res := make([][]int, M)
		for i := 0; i < M; i++ {
			res[i] = make([]int, M)
			res[i][i] = 1
		}
		for power > 0 {
			if power%2 == 1 {
				res = matmul(res, mat)
			}
			mat = matmul(mat, mat)
			power /= 2
		}
		return res
	}

	cntMat := [][]int{make([]int, M)}
	copy(cntMat[0], cnt)

	factor := matpow(matrix, t)
	result := matmul(cntMat, factor)

	ans := 0
	for _, v := range result[0] {
		ans = (ans + v) % MOD
	}
	return ans
}