[toc]
组合基本公式
\[ \binom{n}{k}=\frac{n!}{(n-k)!\cdot k!} \]
\[ \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k} \] \[ \binom{n}{k}=\binom{n}{n-k},n\ge 0, k\in Z \] \[ \binom{n}{k}=\frac{r}{k}\binom{n-1}{k-1}, k\neq 0 \]
组合数的计算
使用内置的\(\Gamma\)函数 \[ \Gamma(s)=\int_o^{+\infty}{x^{s-1}e^{-x}dx} \] 在整数点上满足 \[ \Gamma(n+1)=n! \] 所以可以这样求
1
2
3ll C(ll n,ll m){
return (ll)round(tgamma(n+1)/tgamma(m+1)/tgamma(n-m+1));
}使用杨辉三角形递推
预处理逆元
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29int F[maxn];
int IF[maxn];
int qpow(int x, int n)
{
if (!n)
return 1;
int ans = qpow(x, n / 2);
ans = ans * ans % mod;
if (n & 1)
return ans * x % mod;
return ans;
}
void init()
{
IF[0] = F[0] = 1;
for (int i = 1; i < maxn; i++)
F[i] = F[i - 1] * i % mod;
IF[maxn - 1] = qpow(F[maxn - 1], mod - 2);
for (int i = maxn - 2; i >= 1; i--)
IF[i] = IF[i + 1] * (i + 1) % mod;
IF[1] = 1;
}
int C(int n, int k)
{
if (k < 0 || k > n)
return 0;
return F[n] * IF[k] % mod * IF[n - k] % mod;
}
经典问题
插空法
对于不相邻问题，我们可以使用插空法比如
一共有n个位置，m棵树，两棵树之间要有空位，每棵树都不一样。问你排列方法。首先\(m\)棵树要占\(m\)个坑，这样就剩下了\(n-m\)个坑，剩下的坑会形成\(n-m+1\)个空白，我们的树就可以插到空白里像这样_ 0 _ 0 _ 0 _ 所以结果就是\(A_{n-m+1}^m\)
插板法
使用条件 * 相同的物品分给不同的东西 * 每个东西至少有一个
9个相同的物品放到3个盒子里，每个盒子至少一个物品问有多少种放法
考虑插板法，9个物品之间(不算两边)可以形成8个空隙，两个板子可以把物品分为三块，所以考虑插板，方案数为\(\binom{8}{2}\)。 泛化一下就是\(n\)个物体，分给\(m\)个容器，每个容器至少1个方案数就是\(\binom{n-1}{m-1}\)
如果每个盒子要放\(k\)个，那么可以当\((k-1)\cdot m\)个已经已经放好了
如果每个盒子不要求放的个数，我们可以补\(m\)个球先放进去结果就是\(\binom{n+m-1}{m-1}\)
错排问题
给定\(n\)元素集合\(X\),它的每一个元素都有一个特定的位置,而现在要求求出集合\(X\)的排列中没有一个元素在它指定位置上的排列的数目。
比如当\(n=2\)时有一组\(\{2,1\}\)
首先给出公式\(D_n=(n-1)\cdot(D_{n-1}+D_{n-2})\)
简单证明(非严格)，假如我们有\(n\)个数，我们选择第一个数\(1\)和2配对，这样2可以和1配对，剩下了方案就是\(D_{n-2}\)，如果2不和1位置陪对，那么可以把1位置当2（反正他们不可能在一起）这样方案数就是\(D_{n-1}\)，很显然有\((n-1)\)个平行的情况，所以公式是这个。
容斥原理
容斥原理公式 \[ \left| \bigcup\limits_{i=1}^n{A_i}\right|=\sum_{i=1}^n|A_i|-\sum_{i,j:1\le i\lt j\le n}{|A_i\cap A_j|}+\sum_{i,j,k:\;1\le i \lt j \le k \le n}{|A_i\cap A_j \cap A_k|}-...+(-1)^{n-1}|A_1 \cap ... \cap A_n| \]
大家都知道，如何计算容斥呢。如果我们能快速计算交集的个数，那么可以用二进制枚举所有子集，然后根据元素个数判断是该加上还是减去。（一般我们算的是不合法的方案数，那么就反过来，根据物品种类的数量奇数加，偶数减）
硬币购物
题目大意
共有 4 种硬币。面值分别为\(c_1,c_2,c_3,c_4\)。某人去商店买东西，去了 \(n\) 次，对于每次购买，他带了\(d_1,d_2,d_3,d_4\)枚 \(4\) 种硬币，想购买 \(s\)的价值的东西。请问每次有多少种付款方法。
\(1\le c_i,d_i,s \le 10^5, 1\le n \le 1000\)
分析
用多重背包会超时，我们可以先算出完全背包 \(dp[i]\)代表有购买\(i\)元物品的方案数，\(dp[s-C[i]*(D[i]+1)]\)就是第\(i\)种硬币不合法的方案数。相当于你第\(i\)种硬币已经用了\(D[i]+1\)枚，那就必然不合法了。
参考代码
1 |
|
HDU6397
题目大意
给定\(n,m,k\)，要求个\(m\)个格子填数，使每个数在\([0,n-1]\)范围内，且他们的和为\(k\)。
分析
如果不考虑\([0,n-1]\)这个范围我们就可以使用插板法，相当于\(k\)物体放到\(m\)个格子，但是不要求每个格子有物体方案数就是\(\binom{k+m-1}{m-1}\)。那么考虑限制呢，我们可以使用容斥，比如至少要求\(i\)个数大于等于\(n\)（或者要求\(i\)个数大于等于\(n\)其他数无所谓），那么我们先在那\(i\)个格子中放\(n\)个物品，这些格子就一定大于\(n-1\)满足了条件，剩下了\(k-n\cdot i\)个物品，方案数就是\(\binom{k-n\cdot i+m-1}{m-1}\)，至少要求\(i\)个数大于等于\(n\)的方案数就是 \[ \binom{m}{i}\binom{k-n\cdot i+m-1}{m-1} \] 然后奇数减，偶数加即可
参加代码
1 | void solve() |
CCPC威海2021 M.810975
题目大意
问你有多少个01串满足:长度为\(n\)，有\(m\)个1，最长连续的1长度恰好为\(k\)
分析
我们定义\(f(x)\)为最长连续1的长度小于等于\(x\)的方案数。
答案就是\(f(k)-f(k-1)\)
现在考虑计算\(f(k)\)发现计算\(f(k)\)就是上一题的方法，\(n-m\)个\(0\)留了\(n-m+1\)个空（包含两边），这些空就可以看作盒子数量，然后1的和看做物品数量总和，其中每个盒子最多放\([0,k]\)个物品。
康托展开
基本概念
康托展开主要对一个排列哈希，求一个排列是第几大，具体公式为 \[ \sum\limits_{i=1}^{n-1}{A_i(n-i)!} \] 其中\(A_i\)为\(\sum\limits_{j=i+1}^n{[a_j\lt a_i]}\)
其中\(A_i\)我们可以用\(O(n^2)\)暴力算，也可以用树状数组算。
逆康托展开
类似对进制转换，\(A[i]= x/(n-i)!\)然后取余继续循环。
1 | void init() |
卡特兰数
给定一个数\(N\)，我们要计算由\(2N\)字符能组成多少不同的括号序列。
结论:\(\displaystyle f(n)=\sum_\limits{i=1}^n{f(i-1)\cdot f(n-i)}\)，我们可以这样构造\((p1)p2\) 。不停的扩大\(p1\)的大小，然后使用乘法原理和加法原理即可获得该公式。我们计算这个数列朴素的时间复杂度是\(O(n^2)\)，而其实这个数列有个专门的名字叫做卡特兰数。
一些卡特兰数的公式：
\(\displaystyle C_n=\frac{1}{n+1}\binom {2n} {n}=\binom {2n} {n}-\binom {2n} {n-1}\)
\(C_0=C_1=1,\displaystyle C_n=\frac{4n-2}{n+1}C_{n-1}\)
1 |
|