题解：P11458 [USACO24DEC] All Pairs Similarity P

· · 题解

来点神秘做法。

首先有 \frac{|S \cap T|}{|S \cup T|}=\frac{|S|+|T|}{|S \cup T|}-1。每个位置的答案就是 |a_i|\sum\frac{1}{|a_i \cup a_j|}+\sum\frac{|a_j|}{|a_i \cup a_j|}-n。两部分可以用差不多的方法算，这里就只考虑第一部分。

如果求所有 \sum\frac{1}{|a_i \cup a_j|} 的和，显然可以将出现次数数组和自己做 FWT。然后考虑把一边看作常数，另一边每个位置对答案的贡献是一个常数（也就是把转移画成 DAG 的形式，每条边有一个常数边权，这个就是所有路径权值积的和），然后发现我们要求的就是这个。

然后统计路径权值和正着和倒着是一样的，所以我们把这个 FWT 整个倒过来写就行了。时间复杂度 O(n+k2^k)。

cin>>n>>k;
rep(i,1,n)cin>>a[i],++cnt[a[i]];
repn(S,1<<k)if(S)f[S]=Z(1)/popcnt(S);
repn(i,k)repn(S,1<<k)if(S>>i&1)f[S^(1<<i)]-=f[S];
repn(S,1<<k)scnt[S]=cnt[S],ssum[S]=cnt[S]*popcnt(S);
repn(i,k)repn(S,1<<k)if(S>>i&1)scnt[S]+=scnt[S^(1<<i)],ssum[S]+=ssum[S^(1<<i)];
repn(S,1<<k)g[S]=f[S]*ssum[S],f[S]*=scnt[S];
repn(i,k)repn(S,1<<k)if(S>>i&1)f[S^(1<<i)]+=f[S],g[S^(1<<i)]+=g[S];
repn(S,1<<k)res[S]=f[S]*popcnt(S)+g[S]-n;
rep(i,1,n)cout<<res[a[i]].val()<<'\n';