容斥做题笔记

P1450 [HAOI2008]硬币购物

有 \(4\) 种面值的硬币，买 \(n\) 次东西，每次带了 \(d_i\) 枚 \(i\) 种硬币，想购买价值为 \(s\) 的东西，请问每次有多少种付款方法。

\(n\leq1000\) , \(d_i,s \leq 10^5\)

显然题目其实就是一个多重背包问题，每次暴力做多重背包，复杂度不可接受。

考虑关键在于对于物品限制让我们没有头绪。

如果不考虑物品限制，那么对于每次购物都是一样的，那就变成了一个完全背包。

考虑上物品限制，容斥一下，减去不合法方案。

也就是对于每个方案选择超过数目的方案。

减去第一个超限，第二个超限，第三个超限，第四个超限。

可以使用容斥原理。

const int N = 2e5;
int n, c[8], d[8], s, f[N];
void solve() {
  for (int i = 1; i <= 4; i++)
    d[i] = read();
  s = read();
  int ans = f[s];
  for (int now = 1; now <= (1 << 4) - 1; now++) {
    int cnt = 0, tmp = s;
    for (int i = 1; i <= 4; i++) {
      if ((now >> (i - 1)) & 1) {
        cnt ^= 1;
        tmp -= (d[i] + 1) * c[i];
      }
    }
    if (tmp >= 0)
      ans += (cnt ? -f[tmp] : f[tmp]);
  }
  write(ans);
  putc('\n');
}
signed main() {
  for (int i = 1; i <= 4; i++)
    c[i] = read();
  n = read();
  f[0] = 1;
  for (int i = 1; i <= 4; i++) {
    for (int j = c[i]; j < N; j++) {
      f[j] += f[j - c[i]];
    }
  }
  while (n--)
    solve();
  flush();
  return 0;
}

P3214 [HNOI2011]卡农

从集合 {\(1,2,3....n\)} 中选择 \(m\) 个互不相同的非空集合且所有元素出现次数为偶数的方案数。

答案对 \(10^8 +7\) 取模。

考虑对元素出现次数没有限制的时候怎么做。

显然就是从所有的子集里面选择 \(m\) 个出来，那么答案其实就是 \(\binom{2^n-1}{m}\) 。

考虑有限制的情况，我们考虑动态规划。

题目要求的同种音乐你可以不用管他，最后除以 \(m!\) 即可。

1.所有选出的 \(m\)个子集都不能为空。
2.所有选出的 \(m\) 个子集中，不能存在两个完全一样的集合。
3.所有选出的 \(m\) 个子集中，\(1\) 到 \(n\) 每个元素出现的次数必须是偶数。

我们设立 \(dp_i\) 表示到了选到第 \(i\) 个子集的时候，同时满足以上 \(3\) 点的方案数。

考虑得到了 \(dp_{i-1}\) , 显然这个时候的排列数目就是 \(A_{2^n-1}^{i-1}\) 。

那么考虑去满足条件 \(1\) 与条件 \(2\) 。

条件 \(1\) 显然就是减去 \(dp_{i-1}\) 。

考虑条件 \(2\) ，不能有两个完全一样集合。

那么如果把第 \(j\) 个子集和第 \(i\) 个子集去掉，剩下的 \(i?2\) 个子集可以凑成一个合法的方案，即 \(f[i?2]\) 。

而 \(j\) 有 \(i?1\) 种取值，子集 \(i\) 的取法为\(2^n?1?(i?2)\) ， 即 \(2^n-i+1\) 。

然后可以写出 \(dp\) 方程,线性递推即可。

const int mod = 1e8 + 7, N = 2e6;
int f[N], a[N], n, m, ans;
int power(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1)
      ans = ans * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return ans;
}
signed main() {
  n = read(), m = read();
  int tot = power(2, n) - 1;
  a[0] = f[0] = 1;
  for (int i = 1; i <= m; i++)
    a[i] = a[i - 1] * ((tot - i + 1 + mod) % mod) % mod;
  for (int i = 2; i <= m; i++) {
    f[i] = a[i - 1];
    f[i] -= f[i - 1];
    f[i] = (f[i] - f[i - 2] * (tot - i + 2 + mod) % mod * (i - 1) % mod + mod) %
           mod;
  }
  int k = m;
  ans = m;
  while (--k) {
    ans = ans * k % mod;
  }
  printf("%lld\n", f[m] * power(ans, mod - 2) % mod);
  return 0;
}