[NOI Online #3 提高组]优秀子序列

链接：https://www.luogu.com.cn/problem/CF1284E

题目描述：求在一个序列\(A\)中选一个子集使得任意两个子集下标按位与为\(0\)的子集下标和加\(1\)的莫比乌斯函数和。

题解：将子集下标和为\(i\)的方案数为\(d_{i}\)求出,则\(ans\)可直接求出。\(d\)其实是一个\(a\)的\(log n\)阶子集卷积的形式，然而直接\(FWT\)算子集卷积连暴力\(dp\)都跑不过，\(T\)成\(20\)分。

考虑暴力\(dp\),令\(dp_{S}\)表示子集下标和为\(S\)的方案数，由于子集有序，可以直接枚举补集子集，这样做\(O(3^{log_{2}n})\)，但是能过。

注意\(a_{i}=0\)的情况。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#define mod 1000000007
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
%:pragma GCC optimize("Ofast")
%:pragma GCC optimize("inline")
%:pragma GCC optimize("-fgcse")
%:pragma GCC optimize("-fgcse-lm")
%:pragma GCC optimize("-fipa-sra")
%:pragma GCC optimize("-ftree-pre")
%:pragma GCC optimize("-ftree-vrp")
%:pragma GCC optimize("-fpeephole2")
%:pragma GCC optimize("-ffast-math")
%:pragma GCC optimize("-fsched-spec")
%:pragma GCC optimize("unroll-loops")
%:pragma GCC optimize("-falign-jumps")
%:pragma GCC optimize("-falign-loops")
%:pragma GCC optimize("-falign-labels")
%:pragma GCC optimize("-fdevirtualize")
%:pragma GCC optimize("-fcaller-saves")
%:pragma GCC optimize("-fcrossjumping")
%:pragma GCC optimize("-fthread-jumps")
%:pragma GCC optimize("-funroll-loops")
%:pragma GCC optimize("-fwhole-program")
%:pragma GCC optimize("-freorder-blocks")
%:pragma GCC optimize("-fschedule-insns")
%:pragma GCC optimize("inline-functions")
%:pragma GCC optimize("-ftree-tail-merge")
%:pragma GCC optimize("-fschedule-insns2")
%:pragma GCC optimize("-fstrict-aliasing")
%:pragma GCC optimize("-fstrict-overflow")
%:pragma GCC optimize("-falign-functions")
%:pragma GCC optimize("-fcse-skip-blocks")
%:pragma GCC optimize("-fcse-follow-jumps")
%:pragma GCC optimize("-fsched-interblock")
%:pragma GCC optimize("-fpartial-inlining")
%:pragma GCC optimize("no-stack-protector")
%:pragma GCC optimize("-freorder-functions")
%:pragma GCC optimize("-findirect-inlining")
%:pragma GCC optimize("-fhoist-adjacent-loads")
%:pragma GCC optimize("-frerun-cse-after-loop")
%:pragma GCC optimize("inline-small-functions")
%:pragma GCC optimize("-finline-small-functions")
%:pragma GCC optimize("-ftree-switch-conversion")
%:pragma GCC optimize("-foptimize-sibling-calls")
%:pragma GCC optimize("-fexpensive-optimizations")
%:pragma GCC optimize("-funsafe-loop-optimizations")
%:pragma GCC optimize("inline-functions-called-once")
%:pragma GCC optimize("-fdelete-null-pointer-checks")
using namespace std;
int x,cnt,res,A[400005],dp[400005],N,phi[400005],n;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9')
		c=getchar();
	while ('0'<=c&&c<='9')
	{
		sum=sum*10+c-'0';
		c=getchar();
	}
	return sum;
}
long long fast_pow(long long a,int b)
{
	if (b==0)
		return 1;
	if (b&1)
		return fast_pow(a*a%mod,b/2)*a%mod;
	else
		return fast_pow(a*a%mod,b/2);
}
bool prime[400005];
signed main()
{
	n=read();
	for (int i=1;i<=n;++i)
	{
		x=read();
		N=max(N,x);
		if (x==0)
			cnt++;
		else
			A[x]++;
	}
	N=log(N)/log(2)+1;
	for (int t=1;t<=4e5;++t)
		phi[t]=t;
	for (int t=2;t<=4e5;++t)
		if (!prime[t])
			for (int k=t;k<=4e5;k+=t)
			{
				prime[k]=1;
				phi[k]=phi[k]/t*(t-1);
			}
	dp[0]=1;
    int s;
	for (int k=1;k<=(1<<N)-1;++k)
	{
        s=((1<<N)-1-k);
		for (int t=(1<<N)-1-k;t>0;t=(t-1)&s)
			dp[k+t]=(dp[k+t]+1ll*A[k]*dp[t]%mod)%mod;
		dp[k]=(dp[k]+A[k])%mod;
	}
	for (int k=0;k<=(1<<N)-1;++k)
		res=(res+1ll*phi[k+1]*dp[k]%mod)%mod;
	printf("%lld\n",(res*fast_pow(2,cnt)%mod+mod)%mod);
	return 0;
}