思路
这题的状态还是挺好找的，处理到的下标 idx，第一个序列的 GCD gcd1 以及第二个序列的 GCD gcd2。
idx 从 0 处理到 n-1，每一步有三个分支：每个数字要不不选，要不放到子序列 seq1 中，要不放到子序列 seq2 中。idx 到头后就形成了一组方案。
按照这个处理思路，很适合用 DFS 来做，但是状态空间可能很大，因此还要加记忆化。
GCD 的话就用辗转相除法，辗转相除法可以用正方形填矩形去理解，真的是一旦知道，一辈子都忘不掉了。
代码
class Solution {
public:
int subsequencePairCount(vector<int>& nums) {
// 每个位置要不选，要不不选
// 然后还有 seq1 的 GCD 和 seq2 的 GCD 两个状态，共三个状态
int n=nums.size();
int modulus=(int)(1e9+7);
// 求二者公因数
auto GCD=[&](int a, int b)->int {
if(a<b){
// 保持 a 较大
swap(a, b);
}
// 辗转相除法
int dividend=a;
int div=b;
if(div==0){
return dividend;
}
while(true){
int remainder=dividend%div;
if(remainder==0){
return div;
}
dividend=div;
div=remainder;
}
return -1;
};
// 记忆化
static int memo[201][201][201];
for(int i=0;i<n;i++){
for(int j=0;j<201;j++){
for(int k=0;k<201;k++){
memo[i][j][k]=-1;
}
}
}
auto dfs=[&](auto&& self, int idx, int gcd1, int gcd2)->int {
if(idx>=n){
// 到达 n，说明当前数组中每个数是去是留，放到哪个 seq 已经分配完了，形成了一个方案
// 这个时候才判断 gcd1 是否等于 gcd2
if(gcd1>0&&gcd1==gcd2){
return 1;
}
return 0;
}
if(memo[idx][gcd1][gcd2]!=-1){
return memo[idx][gcd1][gcd2];
}
// 接下来对于 idx，就是三种走向:
// 1. 不选择 idx 对应的元素
// 2. 选择 idx，选入 seq1
// 3. 选择 idx，选入 seq2
// 三种走向的子序列对数量累加起来
int ans = (int)(((long long)self(self, idx+1, gcd1, gcd2)
+ self(self, idx+1, GCD(gcd1,nums[idx]),gcd2)
+ self(self,idx+1, gcd1, GCD(gcd2,nums[idx])))%modulus);
memo[idx][gcd1][gcd2]=ans;
return ans;
};
return dfs(dfs,0,0,0);
}
};
魔法师 07-14 21:191楼
snow 07-14 23:542楼