Description：

给你一个长度为 $n$ 的数组 $s$ ，定义五元组 $(a,b,c,d,e)$ 是合法的当且仅当： $(s_a\text{ or }s_b)\text{ and }s_c\text{ and }(s_d\text{ xor }s_e)=2^i,i\in Z,s_a\text{ and }s_b=0$

对于所有合法的五元组 $(a,b,c,d,e)$ 求 $\sum f(s_a\text{ or }s_b)\times f(s_c)\times f(s_d\text{ xor }s_e)\bmod 10^9+7$ 。

$1\leqslant n\leqslant 10^5,1\leqslant s_i\leqslant 2^{17}$

Solution：

首先用一个 $cnt[s]$ 来统计每种权值出现的次数，然后再求出： $$ cnt_1[s]=\sum_{s_a\text{or}s_b=s,s_a\text{and}s_b=0}cnt[s_a]\times cnt[s_b] $$ 这个就是一个子集卷积，可以用占位多项式法求出。 $$ cnt_2[s]=\sum_{s_a\text{xor}s_b=s}cnt[s_a]\times cnt[s_b] $$ 这个可以 $FWT$ 求出，然后再把 $cnt_1[s]f(s),cnt[s]f(s),cnt_2[s]f(s)$ 与卷积起来就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 1000010

#define MAX 200000

int fib[MAXN];

int s[MAXN];

#define P 1000000007

#define INV2 500000004

void FWT_xor(int f[],int l,int type)

{

	for(int i = 2;i <= l;i = i << 1)

	{

		for(int j = 0;j < l;j += i)

		{

			for(int k = j;k < j + i / 2;++k)

			{

				int u = f[k],t = f[k + i / 2];

				f[k] = (u + t) % P;

				f[k + i / 2] = (u - t + P) % P;

				if(type == -1)

				{

					f[k] = 1ll * f[k] * INV2 % P;

					f[k + i / 2] = 1ll * f[k + i / 2] * INV2 % P;

				}

			}

		}

	}

	return;

}

void FWT_and(int f[],int l,int type)

{

	for(int i = 2;i <= l;i = i << 1)

		for(int j = 0;j < l;j += i)for(int k = j;k < j + i / 2;++k)

			f[k] = (f[k] + 1ll * (P + type) * f[k + i / 2] % P) % P;

	return;

}

void FWT_or(int f[],int l,int type)

{

	for(int i = 2;i <= l;i = i << 1)

		for(int j = 0;j < l;j += i)for(int k = j;k < j + i / 2;++k)

			f[k + i / 2] = (f[k + i / 2] + 1ll * (P + type) * f[k] % P) % P;

	return;

}

int bit[MAXN];

int cnt[MAXN],cnt2[MAXN],cnt3[MAXN];

int f[18][MAXN],g[18][MAXN];

void calc1(int cnt[],int cnt2[],int len)

{

	for(int i = 0;i < len;++i)f[bit[i]][i] = cnt[i];

	for(int i = 0;i <= 17;++i)FWT_or(f[i],len,1);

	for(int i = 0;i <= 17;++i)for(int j = 0;j <= i;++j)

		for(int s = 0;s < len;++s)

			g[i][s] = (g[i][s] + 1ll * f[j][s] * f[i - j][s] % P) % P;

	for(int i = 0;i <= 17;++i)FWT_or(g[i],len,-1);

	for(int s = 0;s < len;++s)cnt2[s] = 1ll * g[bit[s]][s] * fib[s] % P;

	return;

}

int ans[MAXN];

int main()

{

	scanf("%d",&n);

	int mx = 0;

	for(int i = 1;i <= n;++i)scanf("%d",&s[i]);

	for(int i = 1;i <= n;++i)mx = max(mx,s[i]);

	int len = 1;

	for(;len <= mx;len = len << 1);

	for(int i = 1;i < len;++i)bit[i] = bit[i ^ (i & (-i))] + 1;

	fib[0] = 0;fib[1] = 1;

	for(int i = 2;i < MAX;++i)fib[i] = (fib[i - 1] + fib[i - 2]) % P;

	for(int i = 1;i <= n;++i)++cnt[s[i]];

	//for(int i = 0;i < len;++i)cout << cnt[i] << " ";cout << endl;

	calc1(cnt,cnt2,len);

	//for(int i = 0;i < len;++i)cout << cnt2[i] << " ";cout << endl;

	//for(int i = 0;i < len;++i)cout << cnt[i] << " ";cout << endl;

	FWT_xor(cnt,len,1);

	for(int i = 0;i < len;++i)cnt3[i] = 1ll * cnt[i] * cnt[i] % P;

	FWT_xor(cnt,len,-1);FWT_xor(cnt3,len,-1);

	for(int i = 0;i < len;++i)cnt3[i] = 1ll * cnt3[i] * fib[i] % P;

	//for(int i = 0;i < len;++i)cout << cnt3[i] << " ";cout << endl;

	for(int i = 0;i < len;++i)cnt[i] = 1ll * cnt[i] * fib[i] % P;

	//for(int i = 0;i < len;++i)cout << cnt[i] << " ";cout << endl;

	FWT_and(cnt,len,1);FWT_and(cnt2,len,1);FWT_and(cnt3,len,1);

	for(int i = 0;i < len;++i)ans[i] = 1ll * cnt[i] * cnt2[i] % P * cnt3[i] % P;

	FWT_and(ans,len,-1);

	//for(int i = 0;i < len;++i)cout << ans[i] << " ";cout << endl;

	int cur = 1,res = 0;

	while(cur < len)res = (res + ans[cur]) % P,cur = cur << 1;

	cout << res << endl;

	return 0;

}