二项式反演学习笔记

佐世保の时雨 · 2021-12-04 11:37:23 · 个人记录

关于反演

演绎推理是我们在数学中经常遇到的一些方法。对于数列来说，通过原数列计算出新的数列叫作演绎，而通过计算出的数列反推出原数列则被称为反演。

形象化地，如果原数列为 g(x)，新数列是 f(x)，且满足：\large f(x) = \displaystyle\sum^x_{k = 0}a_{x,k} \times g(k)

而反演就是希望我们可以通过 f(x) 来得到 g(x)，即 \large g(x) = \displaystyle\sum^x_{k = 0}b_{x,k} \times f(k)

以上式子经过结合表示为：

数列反演有许许多多种不同的类型，就例如莫比乌斯反演，二项式反演等等。其实，我们发现反演其实就是在解方程，一些方程组有算法上固定的、特殊的解，我们对于这些特殊的算法冠以具体的名字，就例如二项式反演。

二项式反演的常用的公式+证明：

• 辅助公式：

  \large \displaystyle\sum^{n}_{k = 0}\left(-1\right)^k\dbinom{n}{k} = \left[n = 0\right]

  \mathcal Proof:

  首先，当 n = 0 时，式子显然成立。

  当 n > 0 时，由二项式定理可得：\large \displaystyle\sum^n_{k = 0}\left(-1\right)^k\dbinom{n}{k} = \left(1 - \left(-1\right)\right)^n=0

  证毕。

• 公式1(基础公式)：

  \large f(n) = \displaystyle\sum^n_{k=0}\dbinom{n}{k}g(k) \large \Leftrightarrow g(n) = \displaystyle\sum^n_{k=0}\left(-1\right)^{n - k}\dbinom{n}{k}f(k)

  \mathcal Proof:

  首先，我们拿出一个很显然的式子：\large g(n) = \displaystyle\sum^{n}_{k = 0}\left[n - k = 0\right]\dbinom{n}{k}g(k)。

  这应该不需要说明吧

  \large \therefore g(n) = \displaystyle\sum^{n}_{k = 0}\left[n - k = 0\right]\dbinom{n}{k}g(n) \large = \displaystyle\sum^{n}_{k = 0}\displaystyle\sum^{n - k}_{i = 0}(-1)^i\dbinom{n - k}{i}\dbinom{n}{k}g(k) \large = \displaystyle\sum^{n}_{k = 0}\displaystyle\sum^{n - k}_{i = 0}(-1)^i\dbinom{n}{i}\dbinom{n - i}{k}g(k) \large = \displaystyle\sum^{n}_{i = 0}(-1)^i\dbinom{n}{i}\displaystyle\sum^{n - i}_{k = 0}\dbinom{n - i}{k}g(k)

  又 \because \large f(n) = \displaystyle\sum^n_{k=0}\dbinom{n}{k}g(k)

  \large \therefore g(n) = \displaystyle\sum^{n}_{i = 0}(-1)^k\dbinom{n}{k}f(n - k)

  注意此处将原来的 i 换成了 k，便于与原式比较。

  \large \therefore g(n) = \displaystyle\sum^{n}_{k = 0}(-1)^{n - k}\dbinom{n}{k}f(k)

  证毕。

  由于公式2、3证法与公式基础公式大同小异（都是同样的带入方法，只是求和的下界与上界不同），所以就不用证了吧（逃

• 公式2(至多与恰好问题)：

  \large f(n) = \displaystyle\sum^n_{k=m}\dbinom{n}{k}g(k) \large \Leftrightarrow g(n) = \displaystyle\sum^n_{k=m}\left(-1\right)^{n - k}\dbinom{n}{k}f(k)

• 公式3(至少与恰好问题)：

  \large f(n) = \displaystyle\sum^m_{k=n}\dbinom{k}{n}g(k) \large \Leftrightarrow g(n) = \displaystyle\sum^m_{k=n}\left(-1\right)^{k - n}\dbinom{k}{n}f(k)

例题：

• \tt BZOJ\ 2839 集合计数：

  题意：

  给定 n 个元素，相对应的就有 2^n 个集合。现在要在这 2^n 个集合中取出若干集合，使得他们的交集的元素个数为 K，求取法的方案数。对 10^9+7 取模。

  数据范围：n \leq 10^6。

  思路：

  定义 f(x) 表示交集中有 x 个元素被固定选择，剩余元素随意选择的方案数（不去重），定义 g(x) 表示交集恰好有 x 个元素的方案数，则有：

  \large f(x) = \displaystyle\sum^n_{k=x}\dbinom{k}{x}g(k) = \dbinom{n}{x}\left(2^{2^{n - x}} - 1\right) \large g(x) = \displaystyle\sum^n_{k = x}(-1)^{k - x}\dbinom{n}{k}f(k)

  而答案为 g(K)。

  时间复杂度 \Theta\left(n\right)。

  代码：

  // =============================================
  // 暁の水平线に胜利を刻むのです!
  // Author: 佐世保の时雨
  // Blog: https://www.cnblogs.com/SasebonoShigure
  // =============================================
  
  #include <cstdio>
  #include <iostream>
  
  using namespace std;
  
  typedef long long LL;
  
  const int Maxn = 2e6 + 10;
  const LL Mod = 1000000007;
  
  int n, k;
  LL Answer, Pow = 2;
  LL Fact[Maxn], Inv[Maxn];
  
  inline LL Qkpow (LL Base, LL x) {
      LL Pow = 1;
  
      while (x ) {
          if (x & 1 ) {
              Pow = Pow * Base % Mod;
          }
  
          x >>= 1, Base = Base * Base % Mod;
      }
  
      return Pow;
  }
  
  inline LL Getinv (const LL Num) {
      return Qkpow (Num, Mod - 2);
  }
  
  inline LL Getbinom (const int n, const int m) {
      return Fact[n] * Inv[m] % Mod * Inv[n - m] % Mod;
  }
  
  signed main () {
      scanf ("%d %d", &n, &k), Fact[0] = 1;
  
      for (int i = 1; i <= n; ++ i ) {
          Fact[i] = Fact[i - 1] * i % Mod;
      }
  
      Inv[n] = Getinv (Fact[n]);
  
      for (int i = n - 1; ~i; -- i ) {
          Inv[i] = Inv[i + 1] * (i + 1) % Mod;
      }
  
      for (int i = n, Tag = ((n - k) & 1) ? -1 : 1; i >= k; -- i, Tag = -Tag, Pow = Pow * Pow % Mod ) {
          Answer = (Answer + Tag * Getbinom (i, k) * Getbinom (n, i) % Mod * (Pow - 1) % Mod + Mod) % Mod;
  //      printf ("%d\n")
      }
  
      printf ("%lld\n", Answer);
      return 0;
  }

• \tt BZOJ\ 3422 已经没有什么好害怕的了：

  题意：

  有 n 个糖果和 n 个药片，将它们两两配对。每个糖果和药片都有能量值。求糖果的能量大于药片的配对恰好比药片的能量大于糖果的配对多 k 对的方案数。对 10^9+7 取模。

  数据范围：n \leq 2 \times 10^3。0 \leq k \leq n。药片和糖果的能量值在 int 范围内，且 2n 个能量值保证互不相同。

  思路：

  定义 f(x) 表示保证有 x 对糖果的能量大于药片的配对后，剩余 n - x 对糖果和药片随机匹配的方案数（不去重），g(x) 表示恰好有 x 对糖果的能量大于药片的配对的方案数，则有：

  \large f(x) = \displaystyle\sum^n_{k=x}\dbinom{k}{x}g(k) \large g(x) = \displaystyle\sum^n_{k=x}\left(-1\right)^{k - x}\dbinom{k}{x}f(k)

  接下来目标即为求出 f(x) 的表达式。（其中不含 g(x)）

  显然我们需要 DP。

  首先，我们对糖果和药片按能量值从小到大排序。定义 dp_{i,j} 表示将第 i 个糖果配对后，一共有 j 对糖果的能量大于药片的配对。根据定义，我们可以很快得出 \large dp_{i,j} = dp_{i - 1,j} + \left(tot_i - j + 1\right)dp_{i - 1, j - 1}，其中 tot_i 表示能量值比糖果 i 小的药片数。

  所以，\large f(x) = dp_{n,x} \cdot \left(n - x\right)!，答案为 g\left(\dfrac{n+k}{2}\right)。

  时间复杂度 \Theta\left(n^2\right)。

  代码：

  // =============================================
  // 暁の水平线に胜利を刻むのです!
  // Author: 佐世保の时雨
  // Blog: https://www.cnblogs.com/SasebonoShigure
  // =============================================
  
  #include <cstdio>
  #include <iostream>
  #include <algorithm>
  
  using namespace std;
  
  typedef long long LL;
  
  const LL Mod = 1e9 + 9;
  const int Maxn = 2e3 + 10;
  
  int n, k, N;
  int A[Maxn], B[Maxn];
  LL Answer;
  LL f[Maxn][Maxn], Fact[Maxn], Inv[Maxn];
  
  inline LL Qkpow (LL Base, LL x) {
      LL Pow = 1;
  
      while (x ) {
          if (x & 1 ) {
              Pow = Pow * Base % Mod;
          }
  
          x >>= 1, Base = Base * Base % Mod;
      }
  
      return Pow;
  }
  
  inline LL Getinv (const LL Num) {
      return Qkpow (Num, Mod - 2);
  }
  
  inline LL Getbinom (const int n, const int m) {
      return Fact[n] * Inv[m] % Mod * Inv[n - m] % Mod;
  }
  
  signed main () {
      scanf ("%d %d", &n, &k), N = (n + k) >> 1, Fact[0] = 1;
  
      if ((n + k) & 1 ) {
          printf ("0\n");
          return 0;
      }
  
      for (int i = 1; i <= n; ++ i ) {
          Fact[i] = Fact[i - 1] * i % Mod;
      }
  
      Inv[n] = Getinv (Fact[n]);
  
      for (int i = n - 1; ~i; -- i ) {
          Inv[i] = Inv[i + 1] * (i + 1) % Mod;
      }
  
      for (int i = 1; i <= n; ++ i ) {
          scanf ("%d", A + i);
      }
  
      for (int i = 1; i <= n; ++ i ) {
          scanf ("%d", B + i);
      }
  
      sort (A + 1, A + n + 1);
      sort (B + 1, B + n + 1);
      f[0][0] = 1;
  
      for (int i = 1, Count; i <= n; ++ i ) {
          Count = 0, f[i][0] = f[i - 1][0];
  
          for (int j = 1; j <= n; ++ j ) {
              Count += A[i] > B[j];
          }
  
          for (int j = 1; j <= i; ++ j ) {
              f[i][j] = (f[i - 1][j] + max (0, Count - j + 1) * f[i - 1][j - 1] % Mod) % Mod;
          }
      }
  
      for (int i = N, Tag = 1; i <= n; ++ i, Tag = -Tag ) {
          Answer = (Answer + Tag * Getbinom (i, N) * f[n][i] % Mod * Fact[n - i] % Mod + Mod) % Mod;
      }
  
      printf ("%lld\n", Answer);
      return 0;
  }

• \tt BZOJ4665 小w的喜糖：

  题意：

  小w一共买了 n 块喜糖，发给了 n 个人，每个喜糖有一个种类。这时，小w突发奇想，如果这 n 个人相互交换手中的糖，那会有多少种方案使得每个人手中的糖的种类都与原来不同。两个方案不同当且仅当，存在一个人，他手中的糖的种类在两个方案中不一样。

  数据范围：type_i \leq n \leq 2 \times 10^3。

  思路：

  咕咕咕……

  代码：

  // =============================================
  // 暁の水平线に胜利を刻むのです!
  // Author: 佐世保の时雨
  // Blog: https://www.cnblogs.com/SasebonoShigure
  // =============================================
  
  #include <cstdio>
  #include <iostream>
  #include <algorithm>
  
  using namespace std;
  
  typedef long long LL;
  
  const LL Mod = 1e9 + 9;
  const int Maxn = 2e3 + 10;
  
  int n, x;
  int Count[Maxn];
  LL Answer;
  LL f[Maxn][Maxn], Fact[Maxn], Inv[Maxn];
  
  inline LL Qkpow (LL Base, LL x) {
      LL Pow = 1;
  
      while (x ) {
          if (x & 1 ) {
              Pow = Pow * Base % Mod;
          }
  
          x >>= 1, Base = Base * Base % Mod;
      }
  
      return Pow;
  }
  
  inline LL Getinv (const LL Num) {
      return Qkpow (Num, Mod - 2);
  }
  
  inline LL Getbinom (const int n, const int m) {
      return Fact[n] * Inv[m] % Mod * Inv[n - m] % Mod;
  }
  
  signed main () {
      scanf ("%d", &n), Fact[0] = 1;
  
      for (int i = 1; i <= n; ++ i ) {
          scanf ("%d", &x), ++ Count[x];
      }
  
      for (int i = 1; i <= n; ++ i ) {
          Fact[i] = Fact[i - 1] * i % Mod;
      }
  
      Inv[n] = Getinv (Fact[n]);
  
      for (int i = n - 1; ~i; -- i ) {
          Inv[i] = Inv[i + 1] * (i + 1) % Mod;
      }
  
      f[0][0] = 1;
  
      for (int i = 1; i <= n; ++ i ) {
          for (int j = 0; j <= n; ++ j ) {
              for (int k = 0; k <= Count[i] and k <= j; ++ k ) {
                  f[i][j] = (f[i][j] + f[i - 1][j - k] * Getbinom (Count[i], k) % Mod * Inv[Count[i] - k] % Mod) % Mod;
              }
  
          }
      }
  
      for (int i = 0, Tag = 1; i <= n; ++ i, Tag = -Tag ) {
          Answer = (Answer + Tag * f[n][i] % Mod * Fact[n - i] % Mod + Mod) % Mod;
      }
  
      printf ("%lld\n", Answer);
      return 0;
  }

• \tt CF285E\ Positions\ in\ Permutations ：

  题意：

  称一个 1 ∼ n 的排列的完美数为有多少个 i 满足 \left|P_i - i\right| = 1。 求有多少个长度为 n 的完美数恰好为 m 的排列。答案对 10^9 + 7 取模。

  数据范围：1 \leq n \leq 1000，0 \leq m \leq n。

  思路：

  定义 f(x) 表示强制确定 x 个位置为完美的，剩下 n - x 个位置随便放的方案数(不去重)，g(x) 为恰好有 x 个位置为完美的方案数。则有：

  \large f(x) = \displaystyle\sum^n_{k=x}\dbinom{k}{x}g(k) \large g(x) = \displaystyle\sum^n_{k=x}\left(-1\right)^{k - x}\dbinom{k}{x}f(k)

  接下来，我们尝试去得到 f(x)。

  定义 dp_{i,j,0/1,0/1} 表示当前选到了第 i 位，一共有 j 个位置是完美的，是否已经选了 i，是否已经选了 i + 1 的方案数。

  根据定义，我们可以进行分类讨论：

  • 第 i 位是完美的：

    • 第 i 位选 i - 1：

      由状态 \left(i - 1, j - 1, 0, 0\right) 转移到状态 \left(i, j, 0, 0\right)。

      由状态 \left(i - 1, j - 1, 0, 1\right) 转移到状态 \left(i, j, 1, 0\right)。

    • 第 i 位选 i + 1：

      由状态 \left(i - 1, j - 1, 0/1, 0\right) 转移到状态 \left(i, j, 0, 1\right)。

      由状态 \left(i - 1, j - 1, 0/1, 1\right) 转移到状态 \left(i, j, 1, 1\right)。

  • 第 i 位是不完美的：

    由状态 \left(i - 1, j, 0/1, 0\right) 转移到状态 \left(i, j, 0, 0\right)。

    由状态 \left(i - 1, j, 0/1, 1\right) 转移到状态 \left(i, j, 1, 0\right)。

  而 f(x) = \left(dp_{n, x, 0, 0} + dp_{n, x, 1, 1}\right) \times \left(n - x\right)!，由此，我们便可以求出 g(x)。最终答案为 g(m)。

  注意此时 dp_{i,j,0/1,0/1} 可以压维成 dp_{0/1,,j,0/1,0/1}。

  时间复杂度 \Theta \left(n^2\right)。

  代码：

  // =============================================
  // 暁の水平线に胜利を刻むのです!
  // Author: 佐世保の时雨
  // Blog: https://www.cnblogs.com/SasebonoShigure
  // =============================================
  
  #include <cstdio>
  #include <iostream>
  #include <algorithm>
  
  using namespace std;
  
  typedef long long LL;
  
  const LL Mod = 1e9 + 7;
  const int Maxn = 1e3 + 10;
  
  int n, m;
  int Count[Maxn];
  LL Answer;
  LL f[Maxn][Maxn][2][2], Fact[Maxn], Inv[Maxn];
  
  inline LL Qkpow (LL Base, LL x) {
      LL Pow = 1;
  
      while (x ) {
          if (x & 1 ) {
              Pow = Pow * Base % Mod;
          }
  
          x >>= 1, Base = Base * Base % Mod;
      }
  
      return Pow;
  }
  
  inline LL Getinv (const LL Num) {
      return Qkpow (Num, Mod - 2);
  }
  
  inline LL Getbinom (const int n, const int m) {
      return Fact[n] * Inv[m] % Mod * Inv[n - m] % Mod;
  }
  
  signed main () {
      scanf ("%d %d", &n, &m), Fact[0] = 1;
      f[1][0][0][0] = f[1][1][0][1] = 1;
  
      for (int i = 1; i <= n; ++ i ) {
          Fact[i] = Fact[i - 1] * i % Mod;
      }
  
      Inv[n] = Getinv (Fact[n]);
  
      for (int i = n - 1; ~i; -- i ) {
          Inv[i] = Inv[i + 1] * (i + 1) % Mod;
      }
  
      for (int i = 2; i <= n; ++ i ) {
          f[i][0][0][0] = 1;
  
          for (int j = 1; j <= i; ++ j ) {
              f[i][j][0][0] = (f[i - 1][j - 1][0][0] + f[i - 1][j][0][0] + f[i - 1][j][1][0]) % Mod;
              f[i][j][1][0] = (f[i - 1][j - 1][0][1] + f[i - 1][j][0][1] + f[i - 1][j][1][1]) % Mod;
              f[i][j][0][1] = (f[i - 1][j - 1][0][0] + f[i - 1][j - 1][1][0]) % Mod;
              f[i][j][1][1] = (f[i - 1][j - 1][0][1] + f[i - 1][j - 1][1][1]) % Mod;
          }
      }
  
      for (int i = m, Tag = 1; i <= n; ++ i, Tag = -Tag ) {
          Answer = (Answer + Tag * Getbinom (i, m) * (f[n][i][0][0] + f[n][i][1][0]) % Mod * Fact[n - i] % Mod + Mod) % Mod;
      }
  
      printf ("%lld\n", Answer);
      return 0;
  }