Total Characters in String After Transformations II | Leetcode 3337

class Solution {
    using Matrix = array<array<int,26>,26>;
    int MOD = 1e9+7;

    inline Matrix matrixMultiplication(Matrix& A,Matrix& B){
        Matrix res{};
        for(int i=0;i<26;++i){
            for(int j=0;j<26;++j){
                for(int k=0;k<26;++k){
                    res[i][j] = (res[i][j] + (1LL*A[i][k]*B[k][j]) % MOD) % MOD;
                }
            }
        }
        return res;
    }

    inline Matrix matrixExponentiation(Matrix& transformation_matrix,int t){
        Matrix res{};
        //Create identity matrix (to multiply)
        for(int i=0;i<26;++i)
            res[i][i] = 1;
        
        while(t){
            if(t&1)
                res = matrixMultiplication(transformation_matrix,res);
            
            //Square the base & half the exponent
            transformation_matrix = matrixMultiplication(transformation_matrix,transformation_matrix);
            t /= 2;
        }
        return res;
    }
public:
    int lengthAfterTransformations(string s, int t, vector<int>& nums) {
        array<int,26> intial_freq{};
        for(char c: s)
            intial_freq[c-'a']++;

        Matrix transformation_matrix{};
        for(int i=0;i<26;++i){
            //Update column for each transformation
            for(int j=i+1; j<=i+nums[i]; ++j)
                transformation_matrix[j%26][i]++;
        }

        Matrix res = matrixExponentiation(transformation_matrix,t);
        //Now calculate res*intial_freq
        array<int,26> final_array{};
        for(int i=0;i<26;++i){
            for(int j=0;j<26;++j)
                final_array[i] = (final_array[i] + (1LL*res[i][j]*intial_freq[j])% MOD) % MOD;
        }

        int string_size = 0;
        for(int i=0;i<26;++i)
            string_size = (string_size + final_array[i]) % MOD;
        
        return string_size;
    }
};

/*
//JAVA
import java.util.Arrays;

class Solution {
    private static final int MOD = (int)1e9 + 7;
    
    private int[][] matrixMultiplication(int[][] A, int[][] B) {
        int[][] res = new int[26][26];
        for (int i = 0; i < 26; ++i) {
            for (int j = 0; j < 26; ++j) {
                for (int k = 0; k < 26; ++k) {
                    res[i][j] = (int)((res[i][j] + (1L * A[i][k] * B[k][j]) % MOD) % MOD);
                }
            }
        }
        return res;
    }
    
    private int[][] matrixExponentiation(int[][] transformationMatrix, int t) {
        int[][] res = new int[26][26];
        // Create identity matrix
        for (int i = 0; i < 26; ++i) {
            res[i][i] = 1;
        }
        
        while (t > 0) {
            if ((t & 1) == 1) {
                res = matrixMultiplication(transformationMatrix, res);
            }
            transformationMatrix = matrixMultiplication(transformationMatrix, transformationMatrix);
            t >>= 1;
        }
        return res;
    }
    
    public int lengthAfterTransformations(String s, int t, int[] nums) {
        int[] initialFreq = new int[26];
        for (char c : s.toCharArray()) {
            initialFreq[c - 'a']++;
        }
        
        int[][] transformationMatrix = new int[26][26];
        for (int i = 0; i < 26; ++i) {
            for (int j = i + 1; j <= i + nums[i]; ++j) {
                transformationMatrix[j % 26][i]++;
            }
        }
        
        int[][] res = matrixExponentiation(transformationMatrix, t);
        int[] finalArray = new int[26];
        for (int i = 0; i < 26; ++i) {
            for (int j = 0; j < 26; ++j) {
                finalArray[i] = (int)((finalArray[i] + (1L * res[i][j] * initialFreq[j]) % MOD) % MOD);
            }
        }
        
        int stringSize = 0;
        for (int i = 0; i < 26; ++i) {
            stringSize = (stringSize + finalArray[i]) % MOD;
        }
        return stringSize;
    }
}

#Python
MOD = 10**9 + 7

class Solution:
    def matrix_multiplication(self, A, B):
        res = [[0] * 26 for _ in range(26)]
        for i in range(26):
            for j in range(26):
                for k in range(26):
                    res[i][j] = (res[i][j] + A[i][k] * B[k][j]) % MOD
        return res
    
    def matrix_exponentiation(self, transformation_matrix, t):
        res = [[0] * 26 for _ in range(26)]
        # Create identity matrix
        for i in range(26):
            res[i][i] = 1
        
        while t > 0:
            if t & 1:
                res = self.matrix_multiplication(transformation_matrix, res)
            transformation_matrix = self.matrix_multiplication(transformation_matrix, transformation_matrix)
            t >>= 1
        return res
    
    def lengthAfterTransformations(self, s: str, t: int, nums: List[int]) -> int:
        initial_freq = [0] * 26
        for c in s:
            initial_freq[ord(c) - ord('a')] += 1
        
        transformation_matrix = [[0] * 26 for _ in range(26)]
        for i in range(26):
            for j in range(i + 1, i + nums[i] + 1):
                transformation_matrix[j % 26][i] += 1
        
        res = self.matrix_exponentiation(transformation_matrix, t)
        final_array = [0] * 26
        for i in range(26):
            for j in range(26):
                final_array[i] = (final_array[i] + res[i][j] * initial_freq[j]) % MOD
        
        string_size = sum(final_array) % MOD
        return string_size
*/