Re：从零开始的二项式反演

喜闻乐见的公式：

• 公式1：

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

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

  \(\large f(n) = \displaystyle\sum^n_{k=m}\dbinom{n}{k}g(k) \\ \large \Rightarrow 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 \Rightarrow 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 
  #include 
  
  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 
  #include 
  #include 
  
  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 
  #include 
  #include 
  
  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 
  #include 
  #include 
  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;
  }