zcmimi's blog

arrow_back组合数共15篇文章

avatar
zcmimi
2020-07-01 13:58:00

定义

n个元素中取出m个的方案数,记为n\choose mC_n^m

{n\choose m}=\frac{n!}{m!(n-m)!}

帕斯卡法则

{n-1\choose m}+{n-1\choose m-1}={n\choose m}

avatar
zcmimi
2020-03-02

Lucas定理

C_n^m\pmod p\equiv C_{n\mod p}^{m\mod p} \cdot C_{\lfloor n/p\rfloor}^{\lfloor m/p\rfloor}\pmod p

就是一个组合数可以拆成P进制下的乘积

这个算法可以处理当m,n非常大

avatar
zcmimi
2019-12-01

容斥

容斥原理

  • 求具有n个属性之一(并集)的元素的个数

  • 求不具有n个属性中任何一个(交集)的元素的个数

两个集合的并集

|A \bigcup B| = |A|+|B|-|A \bigcap B|

三个集合的并集

$ \begin{aligned

avatar
zc
2020-10-19 16:24:55

查看原题

点击跳转

n个位置中选出m个位置后剩余n-m个位置错排

{n\choose m}\cdot D_{n-m}

avatar
zc
2020-10-16 21:05:56

查看原题

点击跳转

s_i为已经确定的m人中编号不小于i的个数

若存在s_i>n-i+1,显然无解

考虑动态规划,设f(i,j)表示剩下n-m个人中有j个人编号不小于i

\displaystyle f(i,j)=\sum_{k=0}^j f(i+1,j-k)\cdot {j\choose k}, 其中j\le n-s_i-i+1

最终答案为f(1,n-m)

avatar
zc
2020-09-27 21:04:47

查看原题

点击跳转

首先至少需要m-1个空位,然后剩下的n-m+1个位置可以乱放

答案: A_{n-m+1}^m

avatar
zc
2020-09-27 18:39:00

查看原题

点击跳转

题意:

\displaystyle \sum_{i\mod 2=0} {n\choose i}

题解

  1. {n\choose 0}+{n\choose 1}+{n\choose 2}+\dots+{n\choose n}=0
  2. {n\choose 0}-{n\choose 1}+{n\choose 2}-\dots+(-1)^n{n\choose n}=0
  3. {n\choose 0}+{n\choose 2}+{n\choose 4}+\dots={n\choose 1}+{n\choose 3}+{n\choose 5}+\dots=2^{n-1}

证明

二项式定理:

(a+b)^n={n\choose 0}a^n+{n\choose 1}a^{n-1}b+\dots+{n\choose i}a^{n-i}b^i+\dots+{n\choose n}b^n

a=b=1时,可证明1,

a=-1,b=1时,可证明2,

1式+2式可证明3

avatar
zc
2020-07-05 13:10:00
查看原题

点击跳转

此题要求的是S(n,m) \mod 2(第二类斯特林数)

  1. m为偶数,S(n,m) \equiv S(n-1,m-1)

  2. m为奇数,S(n,m) \equiv S(n-1,m-1)+s(n-1,m)

这样的话,相当于:

  1. (x,y)y为奇数时,可以走到(x+1,y+1)(a变换)

  2. 否则可以走到(x+1,y+1)(a变换),或(x+1,y)(b变换)

求从(0,0)走到(n,m)的方案数\pmod 2

这个过程必然走了ma变换,走了n-mb变换

b变换只能在偶数位置出现,那么变换的序列必然是如下形式:

a,b\times ?,a,a,b\times ?,a,a,...,a

也就是在\frac {m+1}2个间隔中插入n-mb,即隔板法

方案数:C(n-m+\frac{m+1}2-1,\frac{m+1}2 -1) \mod 2

还有一个结论:仅当n\&m=m时,C(n,m) \equiv 1 \bmod 2(lucas定理代入即可推出)

avatar
zc
2020-04-26 01:05:00
查看原题

点击跳转

首先,确定最大值和唯一一对的相同的元素

这对元素分别放在最大值的左边和右边

剩下的n-3个元素,有两种选择:

  1. 放在最大值左边
  2. 放在最大值右边

那么就有2^{n-3}种方案

[1,m]中选取n-1个不相同的元素,有m \choose {n-1}种方案

接着在这n-1个元素中选取一个非最大值的元素作为唯一相同那一对,有n-2种方案

那么最终答案就是2^{n-3} \times {m \choose{n-1}} \times (n-2)

avatar
zc
2020-03-11 20:34:00
查看原题

点击跳转

\sum_{i=0}^k {n \choose i} \bmod 2333

p=2333 \sum_{i=0}^k {n \choose i} \bmod p \\ =\sum_{i=0}^k {\left \lfloor \frac np \right \rfloor \choose \left \lfloor \frac ip \right \rfloor} {n \bmod p \choose i\bmod p}\bmod p \\ ={\left \lfloor \frac np \right \rfloor \choose 0}\sum_{i=0}^{p-1}{n \bmod p \choose i}+{\left \lfloor \frac np \right \rfloor \choose 1}\sum_{i=0}^{p-1}{n \bmod p \choose i}+ \cdots+ {\left \lfloor \frac np \right \rfloor \choose \left \lfloor \frac kp \right \rfloor}\sum_{i=0}^{k \bmod p}{n \bmod p \choose i}

f(n,k)=\sum_{i=0}^k {n \choose i}

原式可以转化为:

f(n \bmod p,p-1) \cdot f(\left \lfloor \frac np \right \rfloor,\left \lfloor \frac kp \right \rfloor -1)+{\left \lfloor \frac np \right \rfloor \choose \left \lfloor \frac kp \right \rfloor} f(n\bmod p,k\bmod p)

1/2
Search
search