本文共 1460 字，大约阅读时间需要 4 分钟。

题意：

给你  个数的序列  ，问你  的子序列方案数。

数据范围：  。

题解：

的质因子个数是奇数个，且没有相同的质因子。

的质因子个数是偶数个，且没有相同的质因子。

 表示序列中  的倍数的个数。

 表示  个数形成的非空集合的个数。

这就是莫比乌斯函数。

感受：

关键是分析本质不同的质因子。

代码：

#include
   
    using namespace std;typedef long long ll ;const int maxn = 1e5 + 5 ;const ll mod = 1e9 + 7 ;int n , cnt[maxn] , num[maxn] ;bool vis[maxn] ;int prime[maxn] ;int mu[maxn] ;void get_mu(){   int up = 1e5 ;   int cnt = 0 ;   mu[1] = 1 ;   for(int i = 2 ; i <= up ; i ++)   {     if(!vis[i])  prime[++ cnt] = i , mu[i] = -1 ;     for(int j = 1 ; j <= cnt && prime[j] * i <= up ; j ++)     {       vis[prime[j] * i] = 1 ;       if(i % prime[j] == 0)  break ;        else  mu[i * prime[j]] = -mu[i] ;     }   }}void init(){	int up = 1e5 ;	num[1] = n ;	for(int i = 2 ; i <= up ; i ++)	  for(int j = i ; j <= up ; j += i)	    num[i] += cnt[j] ;}ll qpow(ll a , ll b){   ll ans = 1 ;    a %= mod ;   while(b)   {     if(b & 1)  ans = (ans * a) % mod ;     b >>= 1 , a = (a * a) % mod ;   }   return ans % mod ;}ll cal(int x){	ll ans = 0 ;	ans = qpow(2ll , ll(x)) ;	ans = (ans - 1 + mod) % mod ;	return ans ;}void solve(){	int up = 1e5 ;	ll ans = cal(num[1]) ;	for(int i = 2 ; i <= 1e5 ; i ++)	{		ans += ll(mu[i]) * cal(num[i]) ;		ans %= mod ;	}	ans = (ans + mod) % mod ;	printf("%lld\n" , ans) ;}int main(){	scanf("%d" , &n) ;	memset(cnt , 0 , sizeof(cnt)) ;	memset(num , 0 , sizeof(num)) ;	for(int i = 1 ; i <= n ; i ++)	{		int x ;		scanf("%d" , &x) ;		cnt[x] ++ ;	}	get_mu() ;	init() ;	solve() ;	return 0 ;}
   

转载地址：http://afml.baihongyu.com/