集合子集计数 - 互为倍数关系

集合子集计数 - 互为倍数关系

问题描述：

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

输入描述：

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

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

输出描述：

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

编程语言： C++

算法思路： 动态规划

我们可以用动态规划来解决这个问题。令 dp[i] 表示集合中包含 i 这个元素的所有子集中，符合条件的子集数量。那么最终的答案就是所有 dp[i] 的和。

对于一个元素 i，我们可以将其加入到符合条件的子集中，也可以不加入。如果我们将 i 加入到一个子集中，那么这个子集中的所有元素都必须是 i 的倍数。因此，我们只需要枚举 i 的倍数 j，将 dp[j] 加到 dp[i] 中即可。最后，将 dp[i] 加上 1，表示只包含 i 这个元素的子集也是符合条件的。

最终的时间复杂度为 O(nlogn)，其中 n 是集合中元素的个数。

C++ 代码：

#include <iostream>
#include <vector>
#define MOD 1000000007

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<long long> dp(1000001, 0);
    for (int i = 0; i < n; i++) {
        dp[a[i]]++;
        for (int j = a[i] * 2; j <= 1000000; j += a[i]) {
            dp[a[i]] = (dp[a[i]] + dp[j]) % MOD;
        }
    }
    long long ans = 0;
    for (int i = 1; i <= 1000000; i++) {
        ans = (ans + dp[i]) % MOD;
    }
    cout << ans << endl;
    return 0;
}