https://i.imgur.com/Q6LZOOi.png
Q1:
n<=100, 暴力硬做
Q2/Q4:
矩阵乘法练习
令 x 为 a-z 的个数(size: [26,1]) 可以先求出转移矩阵 A (size: [26,26])
经过一次 transformation 后变为 Ax 为新的 a-z 的个数
则只要用快速幂求出 A^t x 就可以了
Q2可以用 DP 做 O(|s| + t) 的也会过
Q3:
nums[i] <= 200, 所以可以令 DP[x][y] 为 gcd 分别为 x, y 的数量
最后求 DP[1][1] + DP[2][2] + ... + DP[200][200]
吃了一次 TLE 因为觉得 gcd 至少 O(log n) 结果还蛮慢的
改成 preprocess 完所有 gcd(x, y) 就过了
Q3 一开始一直在想要怎么利用 gcd 想不出来就先去做 Q4
回头才发现单纯用 DP 就行了
唯一用到 gcd 的性质是 gcd(x,y) <= min(x,y) for x,y != 0