首页 > 代码库 > 【数论】计数问题的几种基本方法
【数论】计数问题的几种基本方法
一、计数原理
加法原理:n个方法,每个方法有Pi种方案,那么一共方案数为P1 + P2 + P3... + Pn
乘法原理:一件事情有n个步骤,每个步骤需要pi种方案,那么一共有P1 * P2 * P3 * ... * Pn种方案。
容斥原理:集合A,B,C。|A U B U C| = |A| + |B| + |C| - |AB| - |AC| - |BC| + |ABC|。依次类推。
基本的方法就是加加减减,把当个总数计算出来,在扣掉重复的,在加上扣掉重复的重复......
二、组合问题:
组合数C(n, m)的性质:
C(n, 0) = C(n, n) = 1; C(n, k) = C(n, n - k); (这个高中都学过)
C(n, k) + C(n, k + 1) = C(n + 1, k + 1);
C(n, k + 1) = C(n, k) * (n - k) / (k + 1) 这个性质用来处理C(n,m)过程溢出的情况,如果边乘边除可以在一定范围内防止数字的溢出
1、n个数,选k个出来,无关顺序,一个数最多一次,问方案数
C(n, k)
2、n个数,选k个一排,一个数最多选一次,问有几种方案。
C(n,k)先选出k个,然后k进行全排列 * k!。化简后答案为 n! / (n - k) !
3、(a + b) ^ n各项系数(这个高中也学过)
sum{a^(n - k) * b ^ k * C(n, k)} (0 <= k <= n)
4、有重复元素的全排列:
n! / (n1! * n2! * n3!....)
5、可重复选择的组合问题,有n个不同元素,每个元素可以重复选,要选出k个,要保证不同,问能选出几种
设第i个元素选xi次,问题转化为求x1 + x2 + x3 + ... xn = k的解的个数,等价于放k个1,然后分成n份的情况数,利用隔板法答案为C(n + k - 1, k)。