组合数通项公式
[C_n^m=frac{n!}{m!*(n-m)!}
]
组合数递推公式
[C_n^m=C_{n-1}^m+C_{n-1}^{m-1}
]
解释:从n个数里面选m个数,如果第n个数不选,就要从n-1个数里面选m个数
如果第n个数选,那么就要从n-1个数选m-1个数,有点类类似于dp
性质一
[C_n^m=C_n^{n-m}
]
解释:从n个数选m个数,等价于从n个数选n-m个数
性质二
[C_n^0 + C_{n+1}^1 + C_{n+2}^2 + cdots + C_{n+m}^m = sum_{i=0}^m C_{n+i}^i = C_{n+m+1}^m
]
解释:(C_n^0 + C_{n+1}^1 + C_{n+2}^2 + cdots + C_{n+m}^m = C_{n+1}^0 + C_{n+1}^1 + C_{n+2}^2 + cdots + C_{n+m}^m)
(= C_{n+2}^1 + C_{n+2}^2 + cdots + C_{n+m}^m)
(= C_{n+3}^2 + cdots + C_{n+m}^m)
(= C_{n+m+1}^m)
一般方法求组合数
int inv[maxn];
void init()
{
inv[1] = 1;
for(int i = 2; i < maxn; i++)
{
inv[i] = (M-M/i)*inv[M%i]%M;
}
}
int c(int x,int y)
{
int res = 1;
x = min(x,y-x);
for(int i = 1; i <= x; i++)
{
res = (res*(y-i+1)%M*inv[i])%M;
}
return res;
}