CF1436F Sum Over Subsets

题意

给出一个可重集 ，值为 的元素有 个
有两个集合 满足

这两个集合的权值
求所有可能的集合对 的权值之和

题解

考虑令 表示满足 时的答案， 表示满足 时的答案
有
求出 以后，可以莫比乌斯反演得到
即

所以答案

接下来考虑求

先构造集合 有

考虑每一对 对 的贡献

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

• 是同一个元素
  显然 是普通元素
  那么我们从剩下 个元素中选出一个特殊元素，再从剩下的 个元素中任选若干个作为普通元素
  有 种方案，产生 的贡献
• 是不同的元素，注意是元素不同，不是值不同
  显然 是普通元素
  若 是普通元素，类似的有 种方案
  若 是特殊元素，在剩下的 个元素中任选作为普通元素，有 种方案
  共 种方案，产生贡献

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

• 同元素
  乘上值为 的元素个数
  有贡献
• 不同元素
  有贡献

不同的值 之间的贡献
类似的

复杂度为调和级数

代码 codeforces submission 144913462