目录

一，3334. 数组的最大因子得分

二，3335. 字符串转换后的长度 I

三，3336. 最大公约数相等的子序列数量

四，3337. 字符串转换后的长度 II

---

一，3334. 数组的最大因子得分

暴力方法就不演示，这里介绍一个O(n)的做法，前后缀分解，可以预处理nums数组的前缀GCD，LCM和后缀GCD，LCM。然后枚举移除的数，使用前后缀计算总体的GCD和LCM，然后计算出最大值。

代码如下：

class Solution {public long maxScore(int[] nums) {int n = nums.length;long[] sufGcd = new long[n+1];long[] sufLcm = new long[n+1];sufLcm[n] = 1;for(int i=n-1; i>=0; i--){sufGcd[i] = gcd(sufGcd[i+1], nums[i]);sufLcm[i] = lcm(sufLcm[i+1], nums[i]);}long res = sufGcd[0]*sufLcm[0], gc = 0, lc = 1;for(int i=0; i<n; i++){//枚举哪个不选res = Math.max(res, gcd(gc, sufGcd[i+1]) * lcm(lc, sufLcm[i+1]));lc = lcm(lc, nums[i]);gc = gcd(gc, nums[i]);}return res;}long gcd(long x, long y){//(0,x)的最大公约数就是xreturn y==0 ? x : gcd(y, x%y);}long lcm(long x, long y){//(1,x)的最小公倍数就是xreturn x*y/gcd(x, y);}
}

二，3335. 字符串转换后的长度 I

本题有多种做法，这里讲一个简单易懂的，可以发现对于每个字符，它们每次操作产生的字符数量是固定的，所以我们可以先统计26个字符，每个字符的出现次数cnt，然后模拟每次操作所能产生的字符数量，最后cnt数组的和就是答案。

代码如下：

class Solution {int MOD = 1_000_000_007;public int lengthAfterTransformations(String s, int t) {int ans = 0;int[] cnt = new int[26];for(char c : s.toCharArray()){cnt[c-'a']++;}while(t-- > 0){int[] a = cnt.clone();for(int i=1; i<26; i++){a[i] = cnt[i-1]%MOD;}a[0] = cnt[25]%MOD;a[1] = (a[1] + cnt[25])%MOD;cnt = a;}for(int i=0; i<26; i++){ans = (ans + cnt[i])%MOD;}return ans;}
}

三，3336. 最大公约数相等的子序列数量

本题是一道选或不选的问题，分情况讨论，对于第 i 个数：

• 如果不选，即它既不在seq1中，也不在seq2中，接下来问题变成在第 i+1 个数到第 n-1 个数，有多少种分配使得子序列seq1和seq2的GCD相同
• 如果选，分两种情况，它被分配到seq1/seq2中，接下来问题变成在第 i+1 个数到第 n-1 个数，有多少种分配使得子序列seq1和seq2的GCD相同

这样就不断的形成子问题，定义dfs(i，j，k)：从第 i 个数到第 n-1 个数，且此时seq1的GCD为 j ，seq2的GCD为 k 时，使得子序列seq1和seq2的GCD相同的子序列对的总数。

• 如果不选，问题变成在第 i+1 个数到第 n-1 个数，有多少种分配使得子序列seq1和seq2的GCD相同，即 dfs(i+1，j，k)
• 如果选，分两种情况，它被分配到seq1/seq2中，问题变成在第 i+1 个数到第 n-1 个数，有多少种分配使得子序列seq1和seq2的GCD相同，即 dfs(i+1，gcd(j，nums[i])，k) + dfs(i+1， j， gcd(k，nums[i])，nums)
• 求总对数 dfs(i，j，k) = dfs(i+1，j，k) + dfs(i+1，gcd(j，nums[i])，k) + dfs(i+1， j， gcd(k，nums[i])，nums)

代码如下：

class Solution {int MOD = 1_000_000_007;public int subsequencePairCount(int[] nums) {int n = nums.length;memo = new int[n][201][201];for(int i=0; i<n; i++){for(int[] r : memo[i]){Arrays.fill(r, -1);}}return (dfs(0, 0, 0, nums)-1+MOD)%MOD;//-1是删除全部都不选的情况}int[][][] memo;int dfs(int i, int j, int k, int[] nums){if(i == nums.length) return j == k ? 1 : 0;if(memo[i][j][k] != -1) return memo[i][j][k];long res = (long)dfs(i+1, j, k, nums) + dfs(i+1, gcd(j, nums[i]), k, nums) + dfs(i+1, j, gcd(k, nums[i]), nums);return memo[i][j][k] = (int)(res%MOD);}int gcd(int x, int y){return y==0 ? x : gcd(y, x%y);}
} 

递推写法

class Solution {int MOD = 1_000_000_007;public int subsequencePairCount(int[] nums) {int n = nums.length;int m = 0;for(int x : nums) m = Math.max(x, m);long[][][] f = new long[n+1][m+1][m+1];//f[n][i][i] = 1for(int i=0; i<m+1; i++){f[n][i][i] = 1;}for(int i=n-1; i>=0; i--){for(int j=0; j<m+1; j++){for(int k=0; k<m+1; k++){f[i][j][k] = (f[i+1][j][k] + f[i+1][gcd(j, nums[i])][k] + f[i+1][j][gcd(k, nums[i])])%MOD;}}}return (int)(f[0][0][0]-1+MOD)%MOD;}int gcd(int x, int y){return y==0 ? x : gcd(y, x%y);}
} 

四，3337. 字符串转换后的长度 II

本题与T2不同，对于每个字符，它们操作后会转换成连续的nums[i]个字符，且数据范围更大，无法使用上述做法。这里我们可以使用dfs来预处理每个字符，操作 t 次后，所能形成的字符串长度。

dfs记忆化代码：

class Solution {private static final int MOD = 1_000_000_007;public int lengthAfterTransformations(String s, int t, List<Integer> nums) {int[] cnt = new int[26];for(char x : s.toCharArray()){cnt[x-'a']++;}long ans = 0;memo = new int[t+1][26];for(int i=0; i<t+1; i++) Arrays.fill(memo[i], -1);int[] res = new int[26];for(int i=0; i<26; i++){res[i] = dfs(t, i, nums);ans += ((long)res[i] * cnt[i])%MOD;}return (int)(ans%MOD);}int[][] memo;int dfs(int i, int j, List<Integer> nums){if(i == 0) return 1;if(memo[i][j] != -1) return memo[i][j];long res = 0;for(int x=1; x<=nums.get(j); x++){res = (res + dfs(i-1, (j+x)%26, nums))%MOD;}return memo[i][j] = (int)(res%MOD);}
}

但是上述做法的时间复杂度为O(26*26*t)，这肯定会超时间限制，将其转换成dp再来观察观察是否有其他的优化空间（对于本题至少需要一个O(logt)的时间复杂度）.

递推代码：

class Solution {private static final int MOD = 1_000_000_007;public int lengthAfterTransformations(String s, int t, List<Integer> nums) {int[] cnt = new int[26];for(char x : s.toCharArray()){cnt[x-'a']++;}long ans = 0;long[][] f = new long[t+1][26];for(int i=0; i<26; i++)f[0][i] = 1;//预处理每个字母处理t次后，字符串的长度//O(26*25*t)for(int i=1; i<t+1; i++){for(int j=0; j<26; j++){for(int x=1; x<=nums.get(j); x++){f[i][j] = (f[i][j] + f[i-1][(j+x)%26])%MOD;}}}//O(1)for(int k=0; k<26; k++){ans += (f[t][k] * cnt[k])%MOD;}return (int)(ans%MOD);}
}

可以发现 f[i][j] = sum(f[i-1][(j+x)%26])，拿示例一举例:

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]

根据上述公式，可以得到：

将其转换成矩阵的样式：

将 fi0~fi25 矩阵统称为 Fi，那么我们可以得到公式 Fi = M * Fi-1，不断的套用公式，我们可以得到 Fi = M * M * Fi-2 = ... = M^t * F0

这时可以发现，M是一个固定的矩阵（它是通过nums数组计算得来的），M^t 可以使用快速幂来求解，不过这里计算的是矩阵快速幂。

矩阵快速幂优化代码：

class Solution {private static final int MOD = 1_000_000_007;public int lengthAfterTransformations(String s, int t, List<Integer> nums) {int[] cnt = new int[26];for(char x : s.toCharArray()){cnt[x-'a']++;}int[][] m = new int[26][26];for(int i=0; i<26; i++){for(int j=1; j<=nums.get(i); j++){m[i][(i+j)%26]++;}}        int[][] f = new int[26][1];for(int i=0; i<26; i++)f[i][0] = 1;m = pow(m, t, f);long ans = 0;for(int i=0; i<26; i++){System.out.println(cnt[i] + " " + m[i][0]);ans = (ans + (long)cnt[i] * m[i][0])%MOD;}return (int)(ans%MOD);}int[][] pow(int[][] m, int t, int[][] f){int[][] res = f;while(t != 0){if((t&1)!=0){res = mul(m, res);}m = mul(m, m);t >>= 1;}return res;}//矩阵的传参一定要注意：AxB * BxC = AxC !!!int[][] mul(int[][] a, int[][] b){int[][] c = new int[a.length][b[0].length];//c[i][j] += a[i][k] * b[k][j];for(int i=0; i<a.length; i++){for(int k=0; k<a[0].length; k++){if(a[i][k] == 0) continue;for(int j=0; j<b[0].length; j++){c[i][j] = (int)((c[i][j] + (long)a[i][k] * b[k][j])%MOD);}}}return c;}
}