求集合中元素两两互为倍数的子集数量 - C++实现

求集合中元素两两互为倍数的子集数量 - C++实现

问题描述:

米小游拿到了一个集合（集合中元素互不相等）。她想知道，该集合有多少个元素数量大于 1 的子集，满足子集内的元素两两之间互为倍数关系？由于数量可能过大，请对 10 的九次方 + 7 取模。

输入描述:

第一行输入一个正整数 n，代表集合大小。 第二行输入几个正整数 ai，代表集合的元素。

1 ≤ n ≤ 10 的五次方 1 ≤ ai ≤ 10 的六次方

输出描述:

一个整数，代表满足题意的子集数量对对 10 的九次方 + 7 取模的值。

C++ 代码实现:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const long long MOD = 1e9 + 7;

long long countSubsets(vector<int> &nums, int start, vector<int> &multiples) {
  if (start == multiples.size()) {
    return 1;
  }
  long long count = 0;
  // 考虑当前元素
  count = (count + countSubsets(nums, start + 1, multiples)) % MOD;
  // 不考虑当前元素
  count = (count + countSubsets(nums, start + 1, multiples)) % MOD;
  return count;
}

int main() {
  int n;
  cin >> n;
  vector<int> nums(n);
  for (int i = 0; i < n; i++) {
    cin >> nums[i];
  }
  sort(nums.begin(), nums.end());
  long long totalSubsets = 0;
  for (int i = 0; i < n; i++) {
    vector<int> multiples;
    for (int j = i + 1; j < n; j++) {
      if (nums[j] % nums[i] == 0) {
        multiples.push_back(j);
      }
    }
    if (multiples.size() > 0) {
      totalSubsets = (totalSubsets + countSubsets(nums, 0, multiples)) % MOD;
    }
  }
  cout << totalSubsets << endl;
  return 0;
}

思路:

1. 首先将集合中的元素按照从小到大排序，方便查找倍数关系。
2. 对于每个元素，寻找其所有的倍数，如果这些倍数都在集合中，那么就可以将这些倍数的下标加入一个集合中，表示这些元素可以组成一个合法的子集。
3. 然后对于这个集合中的元素，可以通过递归的方式，计算出它们子集的数量。
4. 最后将这些数量相乘即可得到答案。

时间复杂度:

O(n*logn)，其中 n 为集合大小（主要是排序的时间复杂度）。

注意:

• 每次计算子集数量时，都需要将当前元素和它的所有倍数从集合中删除，以避免重复计算。
• 代码中的 countSubsets 函数使用了递归的方式，可以优化为动态规划，以提高效率。

示例:

输入:

3 2 4 8

输出:

3

解释:

集合 {2, 4, 8} 有 3 个满足条件的子集：{2, 4}, {2, 8}, {4, 8}。