第一題是算聯(lián)通塊，兩次dfs即可，太簡單，不細(xì)說了

第二題 算添加刪除mhy的，也挺簡單的，不說了

第三題：

給你一個n的數(shù)組a，數(shù)組中元素不重復(fù)，1<= 元素大小 <=1000000

n為 [1,100000]

求從數(shù)組中挑選多于一個元素的子集（至少兩個元素），使得子集中元素兩兩為倍數(shù)關(guān)系

的方案數(shù) （mod 1000000007）

解法：

把數(shù)組a遞增排序

預(yù)處理這個數(shù)組間 的倍數(shù)關(guān)系 （nlog1000000）

再nlog 去dp一下

dp含義 ：sum[x]表示以x元素作為結(jié)尾的方案數(shù)

轉(zhuǎn)移方程：（條件：a中存在u，且a[i]是u倍數(shù)，u！=a[i]）

sum[a[i]] += sum[u]+1;

代表u結(jié)尾的所有合法子集均添加一個a[i] 的方案數(shù)： sum[u]

以及單一個u的集合加 a[i] 也能構(gòu)成新的合法集合的方案數(shù)： 1

故u對a[i]的貢獻(xiàn)為 sum[u]+1

記得mod一下 ：sum[a[i]]=(sum[a[i]]+sum[u]+1)%mod;

最后，c++ 代碼

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
int n;
int a[1000007];
vector<int>r[1000007];
ll sum[10000007];
bool vis[1000007];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
        vis[a[i]]=1;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=1000000;i++){
        if(vis[i]==0)continue;
        for(int j=i+i;j<=1000000;j+=i){
            if(vis[j])r[j].push_back(i);
        }
    }
    for(int i=2;i<=n;i++){
        for(auto u:r[a[i]]){
            if(vis[u])sum[a[i]]=(sum[a[i]]+sum[u]+1)%mod;
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        ans=(ans+sum[a[i]])%mod;
    }
    cout<<ans;
}