排列数

$n$ 个数字中选 $m$ 个，构成一个排列，问方案数

$P_n^m = n \times (n-1) \times (n-2) \times \cdots \times (n-m+1)$

$P_n^n = n! = n \times (n-1) \times (n-2) \times \cdots \times 1$

组合数

https://en.wikipedia.org/wiki/Combination

$\binom{n}{m} = C_n^m = n \times (n-1) \times (n-2) \times \cdots \times (n-m+1) / m!$

求组合数的方法

直接杨辉三角递推

$C_n^m = C_{n-1}^{m} + C_{n-1}^{m-1}$

$C_n^m = C_n^{n-m}$

如果 $m < 0$ 或 $m > n$ 那么 $C_n^m = 0$

优势：可以模任意数字
优势：预处理之后，可以 $O(1)$ 回答组合数

劣势：时间复杂度是 $O(n^2)$

int c[1020][1020];
int main()
{
	for (int i = 0; i <= n; i++)
	{
		c[i][0] = 1;
		for (int j = 1; j <= i; j++) // 如果 i==0 这层循环是不运行的
		{
			c[i][j] = c[i-1][j] + c[i-1][j-1];
		}
	}
	return 0;
}

在模大质数的情况下，可以预处理阶乘和阶乘的乘法逆元

大质数：n和m小于模数
如果模小质数，需要先Lucas定理

这样可以 $O(1)$ 得到组合数的结果

C(n, m) = fac[n] * invfac[m] % p * invfac[n - m] % p

p = 1000000007
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120

inv(0!) = 1
inv(1!) = 1
inv(2!) = 500000004
inv(3!) = 166666668
inv(4!) = 250000002
inv(5!) = 400000003

C(5, 2) = 5! / 2! / 3! = 10

Lucas定理

小质数：n和m大于模数
组合数模小质数

中国剩余定理

如果组合数模没有平方因子的数，可以转为模质数，再用中国剩余定理合并

组合数模质数，如果n和p都很大，是不可做的

如果p很小，可以Lucas定理把n变小
C(10**9,10**8) % 10007 = ...

如果p很大，但是n很小，可以 $O(n)$ 预处理阶乘，阶乘逆元

如果p很大，n也很大，那么这是不容易做的，有一个 $\sqrt{n} \log n$ 很复杂的方法求 $n! \bmod p$

组合数模质数次幂

转化为计算阶乘模质数次幂的余数是多少，次数是多少？

时间复杂度O(质数次幂)

（可能可以用Wilson定理优化）

乘一个除一个

优势：好写，可以计算 $C(n, m)$ n很大，m很小的情况
一个变种是把除法换成乘法逆元
如果使用乘法逆元，可以分别计算分子的乘积和分母的乘积，最后逆元一次
劣势：慢

int C(int n, int m)
{
	int re = 1;
	for (int i = 0; i < m; i++)
	{
		re = re * (n - i) / (i + 1);
	}
	// for (int i = 1; i <= m; i++)
	// {
	// 	re = re * (n - i + 1) / i;
	// }
	return re;
}

int C(int n, int m)
{
	int x = 1;
	int y = 1;
	for (int i = 0; i < m; i++)
	{
		x = x * (n - i) % p;
		y = y * (i + 1) % p;
	}
	return x * pow(y, p - 2, p) % p;
}

C(6, 3) = 初始值 * 6 / 1 * 5 / 2 * 4 / 3

多重集的全排列

比如 3个a 4个b 全排列方案数？
C(7,3) = C(7,4) = 7! / 3! / 4!

有重复元素的全排列如何计算？
比如 3个a 4个b 5个c 全排列方案数？
C(12, 3) * C(9, 4) * C(5, 5)
C(12, 5) * C(7, 4) * C(3, 3)
12! / 3! / 4! / 5!

全排列除以每个元素重复次数的阶乘

多重集的组合

动态规划
一共有n种元素，第 $i$ 种元素有 $a_i$ 个，希望从所有元素中选取m个，构成一个组合，顺序不同算作相同方案，问方案数

f[i][j] 前i种元素选了j个的方案数，枚举第
i个元素选了几个

f[0][0] = 1
for (int i = 1; i <= n; i++)
{
	for (int j = 0; j <= m; j++)
	{
		for (int k = 0; k <= a[i] && k <= j; k++)
		{
			f[i][j] += f[i - 1][j - k]; // 可以前缀和优化
		}
	}
}

时间复杂度可以优化到 $O(nm)$

多重集的部分排列

动态规划
一共有n种元素，第 $i$ 种元素有 $a_i$ 个，希望从所有元素中选取m个，构成一个排列，顺序不同算作不同方案，问方案数

for (int i = 1; i <= n; i++)
{
	for (int j = 0; j <= m; j++)
	{
		for (int k = 0; k <= a[i] && k <= j; k++)
		{
			f[i][j] += f[i - 1][j - k] * c[j][k];
		}
	}
}

二项式定理

学会高中课本内容即可
$(x + y)^1 = x + y$
$(x + y)^2 = x^2 + 2xy + y^2$
$(x + y)^3 = x^3 + 3x^2y + 3xy^2 + y^3$
$(x + y)^n = \binom{n}{0}x^n y^0 + \cdots + \binom{n}{i}x^{n-i}y^i + \cdots + \binom{n}{n}x^0 y^n$

P2183 [国家集训队]礼物

https://www.luogu.com.cn/problem/P2183

题目背景

一年一度的圣诞节快要来到了。每年的圣诞节小 E 都会收到许多礼物，当然他也会送出许多礼物。不同的人物在小 E 心目中的重要性不同，在小 E 心中分量越重的人，收到的礼物会越多。

题目描述

小 E 从商店中购买了 $n$ 件礼物，打算送给 $m$ 个人，其中送给第 $i$ 个人礼物数量为 $w_i$ 。请你帮忙计算出送礼物的方案数（两个方案被认为是不同的，当且仅当存在某个人在这两种方案中收到的礼物不同）。由于方案数可能会很大，你只需要输出模 $P$ 后的结果。

输入格式

输入的第一行包含一个整数 $P$ ，表示模数。
第二行包含两个整数 $n$ 和 $m$ ，分别表示小 E 从商店购买的礼物数和接受礼物的人数。
第 $3$ 到第 $(m + 2)$ 行，每行一个整数，第 $(i + 2)$ 行的整数 $w_i$ 表示送给第 $i$ 个人的礼物数量。

输出格式

若不存在可行方案，则输出 Impossible，否则输出一个整数，表示模 $P$ 后的方案数。

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

Impossible

提示

样例 1 解释
以 / 分割，/ 前后分别表示送给第一个人和第二个人的礼物编号。 $12$ 种方案详情如下：

1/23 1/24 1/34
2/13 2/14 2/34
3/12 3/14 3/24
4/12 4/13 4/23

数据规模与约定
设 $P= \prod_{i=1}^t p_i^{c_i}$ ， $p_i$ 为质数。

对于 $15\%$ 的数据， $n\leq 15$ ， $m\leq 5$ ， $p_i^{c_i}\leq 10^5$ 。

在剩下的 $85\%$ 数据中，约有 $60\%$ 的数据满足 $t\leq 2$ ， $c_i=1$ ， $p_i\leq 10^5$ ，约有 $30\%$ 的数据满足 $p_i\leq 200$ 。

对于 $100\%$ 的数据， $1\leq n\leq 10^9$ ， $1\leq m\leq 5$ ， $1\leq p_i^{c_i}\leq 10^5$ ， $1\leq w_i \leq P\leq 10^9$ 。

参考代码

题解

先对 $P$ 分解质因数，分解成质数的次幂 $p^c$
如果 $w_i$ 的和大于 $n$ ，直接无解
如果 $w_i$ 的和小于 $n$ ，加一个人
保证 $w_i$ 的和等于 $n$
求 $n! \bmod p^c$ 的余数和次数

求 $1$ 到 $n$ 中不是 $p$ 的倍数的数字的乘积模 $p^c$

求 $1$ 到 $n$ 中 $p$ 的倍数,=

排列数

组合数