P11458 [USACO24DEC] All Pairs Similarity P 题解
_fairytale_
·
·
题解
取 T_i=\overline{S_i}，有：
我们通过容斥求出 $\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;
}
```