# Weekly Contest

日期 2024/10/27

第四題有個 `t <= 10^9` 的限制，當下沒想出來。結果查看討論區有人化為矩陣運算解題，看到提示字矩陣我大概就知道怎麼解了。

- [Find the Maximum Factor Score of Array](https://leetcode.com/problems/find-the-maximum-factor-score-of-array/)
- [Total Characters in String After Transformations I](https://leetcode.com/problems/total-characters-in-string-after-transformations-i/)
- [Find the Number of Subsequences With Equal GCD](https://leetcode.com/problems/find-the-number-of-subsequences-with-equal-gcd/)
- [Total Characters in String After Transformations II](https://leetcode.com/problems/total-characters-in-string-after-transformations-ii/)

### 第一題

class Solution {
public:
    using ll = long long;
    ll ret;
    int ignoreIndex;
    long long maxScore(vector<int>& nums) {
        ret = 0;
        const int n = nums.size();
        for (int i = 0; i <= n; i++) {
            ignoreIndex = i - 1;
            solve(0, nums, 0, 1);
        }
        return ret;
    }
    void solve(int start, vector<int>& nums, ll l2, ll g2) {
        const int n = nums.size();
        if (start == n) {
            ret = max(ret, l2 * g2);
            return;
        }

        if (ignoreIndex == start)
            solve(start + 1, nums, l2, g2);
        else {
            solve(start + 1, nums, gcd(l2, (ll)nums[start]),
                  lcm(g2, (ll)nums[start]));
        }
    }
};

`gcd` 算法特性是只要輸入的參數其中一個為 0，就會回傳另一個數字。
### 第二題

class Solution {
public:
    int lengthAfterTransformations(string s, int t) {
        const int M = 1e9 + 7;
        vector<long long> freq(26, 0);
        for (char c : s)
            freq[c - 'a']++;
        vector<long long> freq2(26, 0);
        for (int i = 0; i < t; i++) {
            fill(freq2.begin(), freq2.end(), 0);
            for (int j = 1; j < 26; j++)
                freq2[j] = freq[j - 1];

            freq2[0] += freq[25];
            freq2[1] += freq[25];
            freq2[0] %= M;
            freq2[1] %= M;
            freq = freq2;
        }

        long long ret = 0;
        for (int i = 0; i < 26; i++) {
            ret += freq[i];
            ret %= M;
        }
        return ret;
    }
};
/*
'z' --> "ab"
'a' --> 'a' + 1

abcyy --> bcdzz --> cde[ab][ab]

v -> w --> x --> y --> z --> ab
*/

照著題目寫即可
### 第三題

### 第四題
這題幾乎都用 Python 解題

class Solution
{
public:
    const int M = 1e9 + 7;
    using aa = array<long long, 26>;
    using a26 = array<aa, 26>;
    unordered_map<int, a26> mm;
    a26 identity;
    a26 mat;
    int lengthAfterTransformations(string s, int t, vector<int> &nums)
    {
        mat = a26({0});
        identity = a26({0});
        for (int i = 0; i < 26; i++)
            identity[i][i] = 1;

        for (int i = 0; i < 26; i++) {
            for (int j = 1; j <= nums[i]; j++) {
                int k = (i + j) % 26;
                mat[k][i]++;
            }
        }
        mm[0] = identity;
        mm[1] = mat;

        a26 matrixPow = matrixCalculate(t);

        aa freq = aa({0});
        aa result = aa({0});
        for (char c : s)
            freq[c - 'a']++;

        for (int i = 0; i < 26; i++) {
            long long r = 0;
            for (int k = 0; k < 26; k++) {
                r += matrixPow[i][k] * freq[k];
                r %= M;
            }
            result[i] = r;
        }
        long long ret = 0;
        for (int i = 0; i < 26; i++) {
            ret += result[i];
            ret %= M;
        }
        return ret;
    }

    a26 matrixCalculate(int n)
    {
        if (n == 0)
            return identity;
        if (n == 1)
            return mat;
        if (mm.find(n) != mm.end())
            return mm[n];

        a26 m1 = matrixCalculate(n / 2);
        a26 m2 = matrixCalculate(n - n / 2);
        a26 ret = a26({0});
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                long long r = 0;
                for (int k = 0; k < 26; k++) {
                    r += m1[i][k] * m2[k][j];
                    r %= M;
                }
                ret[i][j] = r;
            }
        }

        mm[n] = ret;
        return ret;
    }

    void print(a26 &mat)
    {
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                cout << mat[i][j] << " ";
            }
            cout << endl;
        }
    }
};