P11458 [USACO24DEC] All Pairs Similarity P 题解

取

T_i=\overline{S_i}

，有：

\sum_{j}\dfrac{|S_i\cap S_j|}{|S_i\cup S_j|}=|S_i|\sum_{j}\dfrac{1}{|S_i\cup S_j|}+\sum_{j}\dfrac{|S_j|}{|S_i\cup S_j|}-n=|S_i|\sum_{j}\dfrac{1}{k-|T_i\cap T_j|}+\sum_{j}\dfrac{|S_j|}{k-|T_i\cap T_j|}-n

。

我们通过容斥求出

\sum_{j}\dfrac{1}{k-|T_i\cap T_j|}

，后面一项同理。

具体地，我们考虑这样一个错得离谱的算法：

对于每个

T_i

，我们首先对它的所有子集

T_i'

做

f_{T_i'}\gets f_{T_i'}+\dfrac{1}{k-|T_i'|}

，然后对

f

做高维前缀和。最后查询时直接查

f_{T_i}

。

这个算法错误的原因是，设

T=T_i\cap T_j

，每个

T'\subseteq T

都对答案有

\dfrac{1}{k-|T'|}

的贡献，而我们希望总的贡献是

\dfrac{1}{k-|T|}

。其实我们只关心集合大小，于是考虑给每个大小为

t

的集合分配一个系数

a_t

，使之满足我们的期望，即对于每个

T

，都有

\sum_{T'\subseteq T}\dfrac{1}{k-|T'|}=\sum_{t=0}^{|T|}{|T|\choose t}a_t=\dfrac{1}{k-|T|}

。

显然

a_0=\dfrac{1}{k}

，而上面的式子可以得出

a_t=\dfrac{1}{k-t}-\sum_{i=0}^{t-1}{t\choose i}a_i

，因此可以递推

a_i

。

于是我们改为对于每个

T_i

，对它的所有子集

T_i'

做

f_{T_i'}\gets f_{T_i'}+a_{|T_i'|}

，然后对

f

做高维前缀和。最后查询时直接查

f_{T_i}

。

你问怎么“对于每个

T_i

，对它的所有子集

T_i'

做

f_{T_i'}\gets f_{T_i'}+a_{|T_i'|}

”？可以转成对于

S

，用高维后缀和求出有

x

个

T

是

S

的超集，那么

f_{S}

就是

xa_{|S|}

呀！

CPP

#include<bits/stdc++.h>
#define ll long long
#define ppc(x) __builtin_popcount(x)
#define rep(x,qwq,qaq) for(int x=(qwq);x<=(qaq);++x)
#define per(x,qwq,qaq) for(int x=(qwq);x>=(qaq);--x)
using namespace std;
#define m107 1000000007
#define maxn 1051000
#define mod m107
template<typename Tp>
int qp(int x,Tp y) {
	assert(y>=0);
	x%=mod;
	int res=1;
	while(y) {
		if(y&1)res=1ll*res*x%mod;
		x=1ll*x*x%mod;
		y>>=1;
	}
	return res;
}
int inv(int x) {
	return qp(x,mod-2);
}
struct Combinatorics {
#define Lim 2000000
	int fac[Lim+10],invfac[Lim+10];
	Combinatorics() {
		fac[0]=invfac[0]=1;
		rep(i,1,Lim)fac[i]=1ll*fac[i-1]*i%mod;
		invfac[Lim]=inv(fac[Lim]);
		per(i,Lim-1,1)invfac[i]=1ll*invfac[i+1]*(i+1)%mod;
	}
	int C(int n,int m) {
		if(n<m||n<0||m<0)return 0;
		return 1ll*fac[n]*invfac[m]%mod*invfac[n-m]%mod;
	}
	int A(int n,int m) {
		if(n<m||n<0||m<0)return 0;
		return 1ll*fac[n]*invfac[n-m]%mod;
	}
} comb;
template<int MOD>
struct modint {
	int x;
	modint() {
		x=0;
	}
	template<typename T>
	int norm(T y) {
		return (y%MOD+MOD)%MOD;
	}
	template<typename T>
	modint(T y) {
		x=norm(y);
	}
	friend modint operator +(modint a,modint b) {
		return a.x+b.x;
	}
	friend modint operator -(modint a,modint b) {
		return a.x-b.x;
	}
	friend modint operator *(modint a,modint b) {
		return 1ll*a.x*b.x;
	}
	modint& operator +=(modint b) {
		return x=norm(x+b.x),*this;
	}
	modint& operator -=(modint b) {
		return x=norm(x-b.x),*this;
	}
	modint& operator *=(modint b) {
		return x=norm(1ll*x*b.x),*this;
	}
	friend istream& operator >>(istream&is,modint &x) {
		ll v;
		return is>>v,x.x=norm(v),is;
	}
	friend ostream& operator <<(ostream&os,modint x) {
		return os<<x.x,os;
	}
};
using mint=modint<m107>;
int n,k;
int S[maxn],T[maxn];
mint a[maxn],b[maxn];
mint f[maxn],g[maxn];
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>k;
	int U=(1<<k)-1;
	rep(i,1,n)cin>>S[i];
	rep(i,1,n) {
		T[i]=U^S[i];
		f[T[i]]+=1,g[T[i]]+=ppc(S[i]);
	}
	rep(i,0,k-1) {
		rep(mask,0,U) {
			if(~(mask>>i)&1)f[mask]+=f[mask^(1<<i)],g[mask]+=g[mask^(1<<i)];
		}
	}
	a[0]=inv(k);
	rep(s,1,k) {
		a[s]=inv(k-s);
		rep(i,0,s-1)a[s]-=a[i]*comb.C(s,i);
	}
	rep(mask,0,U)f[mask]*=a[ppc(mask)],g[mask]*=a[ppc(mask)];
	rep(i,0,k-1) {
		rep(mask,0,U) {
			if((mask>>i)&1)f[mask]+=f[mask^(1<<i)],g[mask]+=g[mask^(1<<i)];
		}
	}
	rep(i,1,n)cout<<f[T[i]]*ppc(S[i])+g[T[i]]-n<<'\n';
	return 0;
}

P11458 [USACO24DEC] All Pairs Similarity P 题解

文章操作

相关推荐

评论

P11458 [USACO24DEC] All Pairs Similarity P 题解