自动搬运

查看原文

来自洛谷，原作者为

	min_inf 你路过的 与我追逐的 我会等它们重合

搬运于2025-08-24 23:07:29，当前版本为作者最后更新于2024-12-25 16:57:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

来点神秘做法。

首先有 $\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';