目录
3334. 数组的最大因子得分
原题链接
思路分析
AC代码
3335. 字符串转换后的长度 I
原题链接
思路分析
AC代码
3336. 最大公约数相等的子序列数量
原题链接
思路分析
AC代码
3337. 字符串转换后的长度 II
原题链接
思路分析
AC代码
3334. 数组的最大因子得分
原题链接
3334. 数组的最大因子得分
思路分析
直接模拟
时间复杂度：O(N^2 logN)
AC代码
class Solution:def maxScore(self, nums: List[int]) -> int:if len(nums) == 1: return nums[0] ** 2res = 0for i in range(len(nums) + 1):g = 0l = -1for j in range(len(nums)):if i == j: continueg = gcd(g, nums[j])if l == -1:l = nums[j]else:l = l * nums[j] // gcd(l, nums[j])res = max(res, g * l)return res3335. 字符串转换后的长度 I
原题链接
3335. 字符串转换后的长度 I
思路分析
状态机dp
dfs(c, t) 为 一个字符c 在 t次转换后的长度
那么 设x 为变成 ab 所需次数
如果 t < x，那么返回1
否则返回 dfs('a', t - x) + dfs('b', t - x)
时间复杂度：O(U t), U 为字符集大小
AC代码
P = 10**9+7
@cache
def dfs(c: chr, t: int) -> int:x = ord('z') - ord(c) + 1if t < x: return 1return (dfs('a', t - x) + dfs('b', t - x)) % P
class Solution:def lengthAfterTransformations(self, s: str, t: int) -> int:cnt = Counter(s)res = 0for ch, c in cnt.items():res += dfs(ch, t) * c % Pif res >= P:res -= Preturn res3336. 最大公约数相等的子序列数量
原题链接
3336. 最大公约数相等的子序列数量
思路分析
线性dp
定义 f(i, j, k) 为 前 i 个数能够拆出的 <seq1, seq2> 的对数，其中gcd(seq1) = j, gcd(seq2) = k
那么 对于nums[i]，可以加入seq1也可以加入seq2，也可以不加
可以得到三个递推式子
f(i + 1, gcd(j, nums[i], k) += f(i, j, k)
f(i + 1, j, gcd(nums[i], k)) += f(i, j, k)
f(i + 1, j, k) += f(i, j, k)
时间复杂度：O(N M^2 + M^M logM)
AC代码
constexpr int P = 1e9 + 7;
constexpr int N = 201;
int f[2][N][N], g[N][N];
auto INIT = [](){for (int i = 0; i < N; ++ i)for (int j = 0; j < N; ++ j) {g[i][j] = gcd(i, j);}return 0;
}();class Solution {
public:int subsequencePairCount(vector<int>& nums) {int n = nums.size();int M = *max_element(nums.begin(), nums.end());memset(f, 0, sizeof f);f[0][0][0] = 1;for (int i = 0; i < n; ++i) {int v = nums[i];memset(f[(i + 1) & 1], 0, sizeof f[(i + 1) & 1]);for (int x = 0; x <= M; ++x) {for (int y = 0; y <= M; ++y) {f[(i + 1) & 1][g[x][v]][y] = (f[(i + 1) & 1][g[x][v]][y] + f[i & 1][x][y]) % P;f[(i + 1) & 1][x][g[y][v]] = (f[(i + 1) & 1][x][g[y][v]] + f[i & 1][x][y]) % P;f[(i + 1) & 1][x][y] = (f[(i + 1) & 1][x][y] + f[i & 1][x][y]) % P;}}}int res = 0;for (int x = 1; x <= M; ++x) {res = (res + f[n & 1][x][x]) % P;}return res;}
};3337. 字符串转换后的长度 II
原题链接
3337. 字符串转换后的长度 II
思路分析
矩阵快速幂优化状态机dp
很板的矩阵快速幂优化状态机dp
我们根据 nums[] 去填转移矩阵就行了，没什么说的
如果不会矩阵快速幂优化状态机dp：矩阵快速幂及应用实战[C/C++]_c++矩阵快速幂-CSDN博客
时间复杂度：(26^3) * log(t)
AC代码
constexpr int P = 1E9 + 7;
using i64 = long long;
struct Matrix {int m, n;std::vector<std::vector<int>> g;Matrix(int _m, int _n) : m(_m), n(_n), g(_m, std::vector<int>(_n)){}Matrix(const std::vector<std::vector<int>> &_init) : m(_init.size()), n(_init[0].size()), g(_init) {}Matrix(const Matrix &a) : Matrix(a.g) {}void init() {assert(m == n); for (int i = 0; i < m; ++ i)g[i].assign(m, 0), g[i][i] = 1;}const std::vector<int>& operator [] (int i) const {assert(i < m);return g[i];}void show() const {for (int i = 0; i < m; ++ i)for (int j = 0; j < n; ++ j) std::cout << g[i][j] << " \n"[j + 1 == n]; std::cout << '\n';}friend inline Matrix operator * (const Matrix &a, const Matrix &b) {int m = a.m, n = b.n, t = a.n;Matrix res(m, n);for (int i = 0; i < m; ++ i)for (int k = 0; k < t; ++ k)for (int j = 0; j < n; ++ j) res.g[i][j] = (res.g[i][j] + 1LL * a[i][k] * b[k][j] % P) % P;return res;}friend inline Matrix power(Matrix a, i64 b) {Matrix res(a.m, a.m);res.init(); for (; b; b >>= 1, a = a * a) if (b & 1)res = res * a;return res;}
};class Solution {
public:int lengthAfterTransformations(string s, int t, vector<int>& nums) {/*f[t][c] = f[t - 1][] + f[][] + f[][]...*/std::vector<std::vector<int>> help(26, std::vector<int>(26));for (int i = 0; i < 26; ++ i) {for (int j = 1; j <= nums[i]; ++ j) {int nxt = (i + j) % 26;help[nxt][i] = 1;}}Matrix h(help);std::vector<std::vector<int>> cnt(26, std::vector<int>(1));for (char ch : s) {++ cnt[ch - 'a'][0];}Matrix c(cnt);auto g = power(h, t) * c;int res = 0;for (int i = 0; i < 26; ++ i) {res += g[i][0];if (res >= P) {res -= P;}}return res;}
};
