简单题啊，为啥我去年不会呢？

Solution

首先 $\frac{|x\cap y|}{|x\cup y|}=\frac{|x|+|y|}{|x\cup y|}-1$，于是原题即求 $|a_i|\sum_j\frac{1}{|a_i\cup a_j|}+\sum_j\frac{|a_j|}{|a_i\cup a_j|}-n$。

这个分数看起来是没啥有用的性质的，我们直接将原问题强化为如下问题：

给定集合幂级数 $f,g$，$\forall S\subseteq U=\{0,1,\cdots,k-1\}$ 求 $h_S=\sum\limits_{T\subseteq U}f_Tg_{S\cup T}$。

考虑容斥掉 $S\cup T$ 的限制。进行一点简单的推导：

$$\begin{aligned} h_S&=\sum_{T\subseteq U}f_Tg_{S\cup T}\\ &=\sum_{S\subseteq R}g_R\sum_{T\subseteq R}f_T[S\cup T=R]\\ &=\sum_{S\subseteq R}g_R\sum_{T\subseteq R}f_T\sum_{P\subseteq R}(-1)^{|R|-|P|}[S\cup T\subseteq P]\\ &=\sum_{S\subseteq R}g_R\sum_{T\subseteq R}f_T\sum_{P\subseteq R}(-1)^{|R|-|P|}[S\subseteq P][T\subseteq P]\\ &=\sum_{S\subseteq P}\Big(\sum_{P\subseteq R}(-1)^{|R|-|P|}g_R\Big)\Big(\sum_{T\subseteq P}f_T\Big) \end{aligned}$$

这些都是可以直接算的，复杂度 $O(k2^k)$。

Code

bool Mst;
#include<bits/stdc++.h>
using namespace std;
using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128;
using u128=__uint128_t;
using pii=pair<int,int>;
#define fi first
#define se second
#define popc __builtin_popcount
constexpr int N=5e5+5,M=20,mod=1e9+7;
inline ll add(ll x,ll y){return (x+=y)>=mod&&(x-=mod),x;}
inline ll Add(ll &x,ll y){return x=add(x,y);}
inline ll sub(ll x,ll y){return (x-=y)<0&&(x+=mod),x;}
inline ll Sub(ll &x,ll y){return x=sub(x,y);}
inline ll qpow(ll a,ll b){
	ll res=1;
	for(;b;b>>=1,a=a*a%mod)
		if(b&1)res=res*a%mod;
	return res;
}
int n,m,U,a[N];ll inv[M+1],f[1<<M],g[1<<M],h[1<<M],ans1[1<<M],ans2[1<<M];
inline void PreSum(ll *f){
	for(int i=1;i<=U;i<<=1)
		for(int j=0;j<=U;j+=i<<1)
			for(int k=0;k<i;k++)
				Add(f[i|j|k],f[j|k]);
}
inline void PreDif(ll *f){
	for(int i=1;i<=U;i<<=1)
		for(int j=0;j<=U;j+=i<<1)
			for(int k=0;k<i;k++)
				Sub(f[i|j|k],f[j|k]);
}
inline void SufSum(ll *f){
	for(int i=1;i<=U;i<<=1)
		for(int j=0;j<=U;j+=i<<1)
			for(int k=0;k<i;k++)
				Add(f[j|k],f[i|j|k]);
}
inline void SufDif(ll *f){
	for(int i=1;i<=U;i<<=1)
		for(int j=0;j<=U;j+=i<<1)
			for(int k=0;k<i;k++)
				Sub(f[j|k],f[i|j|k]);
}
inline void work(const ll *f,const ll *g,ll *h){
	static ll F[1<<M],G[1<<M];
	for(int i=0;i<=U;i++)F[i]=f[i];
	for(int i=0;i<=U;i++)G[i]=g[i];
	PreSum(F),SufDif(G);
	for(int i=0;i<=U;i++)F[i]=F[i]*G[i]%mod;
	SufSum(F);
	for(int i=0;i<=U;i++)h[i]=F[i];
}
bool Med;
int main(){
	cerr<<abs(&Mst-&Med)/1048576.0<<endl;
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m,U=(1<<m)-1;
	inv[1]=1;
	for(int i=2;i<=m;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	for(int i=1;i<=n;i++)cin>>a[i],++f[a[i]],g[a[i]]+=popc(a[i]);
	for(int i=0;i<=U;i++)h[i]=inv[popc(i)];
	work(f,h,ans1),work(g,h,ans2);
	for(int i=1;i<=n;i++)cout<<sub(add(popc(a[i])*ans1[a[i]]%mod,ans2[a[i]]),n)<<'\n';
	return 0;
}