CF1436F Sum Over Subsets

题意

给出一个可重集 $S$，值为 $i$ 的元素有 $freq_i$ 个
有两个集合 $A,B$ 满足

• $B\subset A\subseteq S$
• $|B|=|A|-1$
• $\gcd\limits_{x\in A}x=1$

这两个集合的权值 $w(A,B)=\sum\limits_{x\in A}x\sum\limits_{y\in B}y$
求所有可能的集合对 $(A, B)$ 的权值之和

$1\le a_i\le10^5,freq_i\le10^9$

题解

考虑令 $f_i$ 表示满足 $\gcd\limits_{x\in A}x=i$ 时的答案，$g_i$ 表示满足 $i\mid\gcd_{x\in A}x$ 时的答案
有 $g_i=\sum\limits_{i\mid j}f_j$
求出 $g$ 以后，可以莫比乌斯反演得到 $f$
即 $f_i=\sum\limits_{j\mid i}\mu(j)\times g_j$

所以答案 $\text{Ans}=\sum\limits_{1\le i}\mu(i)\times g_i$

接下来考虑求 $g_i$

先构造集合 $S'=\{x|x\in S,i\mid x\}$ 有 $$\begin{aligned} g_i&=\sum_{B\subset A\subseteq S',|B|=|A|-1}w(A,B)\\ &=\sum_{B\subset A\subseteq S',|B|=|A|-1}\sum_{x\in A}\sum_{y\in B}x\times y \end{aligned}$$

考虑每一对 $(x\in A, y\in B)$ 对 $g_i$ 的贡献

在集合 $A$ 中但不再集合 $B$ 中的元素称为特殊元素，在集合 $A$ 和 $B$ 中的称为普通元素
分两种情况讨论：

• $x, y$ 是同一个元素
  显然 $x$ 是普通元素
  那么我们从剩下 $|S'|-1$ 个元素中选出一个特殊元素，再从剩下的 $|S'|-2$ 个元素中任选若干个作为普通元素
  有 $(|S'|-1)\times 2^{|S'|-2}$ 种方案，产生 $(|S'|-1)\times 2^{|S'|-2}\times x^2$ 的贡献
• $x, y$ 是不同的元素，注意是元素不同，不是值不同
  显然 $y$ 是普通元素
  若 $x$ 是普通元素，类似的有 $(|S'|-2)\times 2^{|S'|-3}$ 种方案
  若 $x$ 是特殊元素，在剩下的 $|S'|-2$ 个元素中任选作为普通元素，有 $s^{|S'|-2}$ 种方案
  共 $(|S'|-2)\times 2^{|S'|-3}+s^{|S'-2|}$ 种方案，产生贡献 $[(|S'|-2)\times 2^{|S'|-3}+s^{|S'|-2}]\times x\times y$

回到本题，由于 $freq$ 特别大，把值相同的元素放在一起考虑
相同值 $x$ 之间的贡献有两种

• 同元素
  乘上值为 $x$ 的元素个数
  有贡献 $(|S'|-1)\times 2^{|S'|-2}\times x^2\times freq_x$
• 不同元素
  有贡献 $\left[(|S'|-2)\times 2^{|S'|-3}+s^{|S'|-2}\right]\times x^2\times freq_x\times (freq_x-1)$

不同的值 $x, y$ 之间的贡献
类似的 $\left[(|S'|-2)\times 2^{|S'|-3}+s^{|S'|-2}\right]x\times y\times freq_x\times freq_y$

$$\begin{aligned}&\sum_{x,y\in S',x\not =y}\left[(|S'|-2)\times 2^{|S'|-3}+s^{|S'|-2}\right]\times x\times y\times freq_x\times freq_y\\&=\left[(|S'|-2)\times 2^{|S'|-3}+s^{|S'|-2}\right]\left[(\sum_{x\in S'}x\times freq_x)^2-\sum_{x\in S'}(x\times freq_x)^2\right]\end{aligned}$$

复杂度为调和级数

代码 codeforces submission 144913462