C++(g++ 7.5.0) 解法, 执行用时: 9ms, 内存消耗: 1064K, 提交时间: 2022-08-08 07:55:14

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll N=11,M=65;
const ll mod=1e9+9;
ll R[N],dp[M][1<<N];
int n;
inline ll dfs(ll s,ll pos){
	ll &ans=dp[pos][s];
	if(pos<=0)
		return 1;
	if(ans)
		return ans;
	int sp=s;
	for(int i=0; i<n; i++)
		if((s&(1<<i)) && (R[i]&(1ll<<(pos-1))))
			sp^=(1<<i);
	ans = (ans+dfs(sp,pos-1))%mod;
	for(int i=0; i<n; i++){
		if((s&(1<<i))){
			if(!(R[i]&(1ll<<(pos-1))))
				continue;
			ans=(ans+dfs(sp^(1ll<<i),pos-1))%mod;
		}
		else
			ans=(ans+dfs(sp,pos-1))%mod;
	}
	return ans;
}

int main(){
	cin>>n;
	for(int i=0; i<n; i++)
		cin>>R[i];
	cout<<dfs((1<<n)-1,60ll);
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 8ms, 内存消耗: 1004K, 提交时间: 2019-09-10 17:19:50

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+9;
int  f[70][2100];
ll a[20];
int n;
int  dfs(int k,int now)
{
    if(k<0) return 1;
    int x=f[k][now];
    if(x) return x; 
    int nxt=now;
    for(int i=1;i<=n;i++)
     if(a[i]>>k&1) nxt|=1<<i;
    x=dfs(k-1,nxt);//全0
    for(int i=1;i<=n;i++)//填1
    {
        if(now>>i&1)
         x=(x+dfs(k-1,nxt))%mod;
        else if(nxt>>i&1)
         x=(x+dfs(k-1,nxt^(1<<i)))%mod;
    }
    return f[k][now]=x;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    cout<<dfs(62,0)<<endl;
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 8ms, 内存消耗: 1244K, 提交时间: 2020-03-07 22:30:58

#include<bits/stdc++.h>
using namespace std;
int mod=1e9+9;
int dp[70][2000],n;
long long r[15];
int dfs(int d,int now)
{
	if(d<0) return 1;
	int ans=dp[d][now];
	if(ans!=-1) return ans;
	int nxt=now;
	for(int i=0;i<n;i++)
	if(r[i]>>d&1)
	nxt|=1<<i;
	ans=dfs(d-1,nxt);
	for(int i=0;i<n;i++)
	{
		if(now>>i&1)
		ans=(ans+dfs(d-1,nxt))%mod;
		else if(nxt>>i&1)
		ans=(ans+dfs(d-1,nxt^(1<<i)))%mod; 
	}
	return dp[d][now]=ans;
}
int main()
{
	cin>>n;
	memset(dp,-1,sizeof(dp));
	for(int i=0;i<n;i++)
	cin>>r[i];
	cout<<dfs(60,0)<<endl;
	return 0;
}