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

2023-11-22 13:01:15

喜闻乐见的公式：

公式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 <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;
}
```

码农公寓

喜闻乐见的公式：

公式1：

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

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

例题：

\(\tt BZOJ\ 2839\) 集合计数：

题意：

思路：

代码：

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

题意：

思路：

代码：

\(\tt BZOJ4665\) 小w的喜糖：

题意：

思路：

代码：

\(\tt CF285E\ Positions\ in\ Permutations\) ：

题意：

思路：

代码：

相关文章