组合数
1. 求组合数
根据不同的数据范围，求组合数也可以运用不同的方法。由于这是中学的内容，所以这里就不详细介绍了。
求解的总的式子：
\(C_a^b=\frac{a!}{b!(a-b!}\\(a\个物品中选出\(b\个的方案数。
(1 递推法
\(C_a^b=C_{a-1}^b+C_{a-1}^{b-1}\\(C_{a-1}^k,k\in[0,b]\的结果，那么当前有\(a\个物品时，第\(a\个物品要么被选，要么不被选中。若被选中，则方案一共有\(C_{a-1}^{b-1}\个，若不被选中，则方案有\(C_{a-1}^b\个，方案累加，得证。 \(O(n^2\
void init({
for (int i=0;i<N;++i{
for (int j=0;j<=i;++j{
if (!j C[i][j] = 1;
else{
C[i][j] = (C[i-1][j-1] + C[i-1][j] % M;
}
}
}
}(2 通过预处理逆元的方式求组合数
\(a!,\frac{1}{b!},\frac{1}{(a-b!}\，然后再相乘。 \(O(n\log n\
int n;
const int N = 1e5 + 5;
const ll M = 1e9 + 7;
ll fac[N], invf[N];// 阶乘 阶乘的逆元
void init({
fac[0] = invf[0] = 1LL;
for (int i=1;i<N;++i{
fac[i] = fac[i-1] * i % M;
invf[i] = invf[i-1] * qmi(i, M-2, M % M;
}
}
int main(void{
scanf("%d", &n;
init(;
ll a, b;
for (int i=1;i<=n;++i{
scanf("%lld%lld", &a, &b;
ll ans = fac[a] * invf[b] % M * invf[a - b] % M;
printf("%lld\n", ans;
}
return 0;
}(3 分解质因数法求组合数（高精度）
\(a!\写成\(a!=p_1^{a_1}\times p_2^{a_2}\times ...\times p_k^{a_k}\的形式，那么\(C_a^b\的答案肯定可以写成\(C_a^b=p_1^{b_1}\times p_2^{b_2}\times ...\times p_k^{b_k},\forall i\in[1,k],b_i\leq a_i\。 \(s_i\为\(a!\中包含的质因子\(p_i\的个数减去\(b!,(a-b!\中包含的\(p_i\的个数，则\(C_a^b=\prod_{i=1}^{k} p_i^{s_i}\。 \(a!\包含的质因子个数为多少呢？答案是\(\lfloor\frac{a}{p}\rfloor+\lfloor\frac{a}{p^2}\rfloor+\lfloor\frac{a}{p^3}\rfloor...\。
代码：
const int N = 5000 + 5;
int p[N], sa[N], cnt;
bool st[N];
void Euler(int n{
for (int i=2;i<=n;++i{
if (!st[i] p[++cnt] = i;
for (int j=1;p[j]<=n/i;++j{
st[p[j] * i] = true;
if (i % p[j] == 0 break;
}
}
}
int get(int n, int p{
int res = 0;
while (n{
res += n/p;
n/=p;
}
return res;
}
vector<int> mul(vector<int>& A, int b{
vector<int> res; int t = 0;
for (int i=0;i<A.size(;++i{
t += A[i]*b;
res.push_back(t % 10, t /= 10;
}
while (t{ res.push_back(t%10, t /= 10;}
while (res.back(==0 && res.size(>1 res.pop_back(;
return res;
}
int main(void{
int a, b;
scanf("%d%d", &a, &b;
Euler(a;
for (int i=1;i<=cnt;++i{
int cur = p[i];
sa[i] = get(a, cur - get(a-b, cur - get(b, cur;
}
vector<int> res;
res.push_back(1;
for (int i=1;i<=cnt;++i{
for (int j=0;j<sa[i];++j{
res = mul(res, p[i];
}
}
for (int i=res.size(-1;i>=0;--i{
printf("%d", res[i];
}
puts("";
return 0;
}(4 Lucas定理求组合数
Lucas定理：\(C_a^b \equiv C_{a\mod p}^{b \mod p}\times C_{a/p}^{b/p} (\mod p\
代码
\(C_a^b=\frac{a!}{b!(a-b!}=\frac{a\times (a-1\times...\times (a-b+1}{b!}\求得
ll C(ll a, ll b, ll p{
if (b > a return 0;
ll res = 1;
for (int i=1, j=a;i<=b;++i, --j{
res = res * j % p; // 分子
res = res * qmi(i, p-2, p % p; // 分母
}
return res;
}
ll lucas(ll a, ll b, ll p{
if (a<p && b<p return C(a, b, p;
return C(a%p, b%p, p * lucas(a/p, b/p, p % p;
}(5 取对数求组合数（可能有浮点误差）
此种方法大概可以计算1000以内的组合数。
\(m\leq \frac{n}{2}\吧，否则因为\(C(n,m=C(n,m-n\，令\(m=m-n\。 \(x=\ln C(n,m=\ln (\frac{n!}{m!(n-m!}=\sum\limits _{i=1}^n\ln i-\sum\limits _{i=1}^m\ln i-\sum\limits _{i=1}^{n-m}\ln i\\(\ln n\，则\(C(n,m=e^x\。
2. 常用公式
(1 二项式定理
\[(x+y^n=\left(\begin{array}{} n\\ 0 \end{array}\rightx^ny^0+\left(\begin{array}{} n\\ 1 \end{array}\rightx^{n-1}y^1+...+\left(\begin{array}{} n\\ n-1 \end{array}\rightx^1y^{n-1}+\left(\begin{array}{} n\\ n \end{array}\rightx^0y^n \]
\((x+y^n=\sum\limits_{k=0}^n\left(\begin{array}{} n\\ k \end{array}\rightx^{n-k}y^k=\sum\limits_{k=0}^n\left(\begin{array}{} n\\ k \end{array}\rightx^{k}y^{n-k}\\(\left(\begin{array}{} n\\ k \end{array}\right=C_n^k=\frac{n!}{k!(n-k!}\。 \((1+x^n=\sum\limits_{k=0}^n C_n^kx^k\。 \((1-x^n=\sum\limits_{k=0}^n (-1^kC_n^kx^k\
(2 其他的一些小公式
\(C_n^0+C_n^1+...+C_n^n=2^n\（从\(n\取任意个数，显然二进制取或不取） \(C_a^b=C_{a-1}^b+C_{a-1}^{b-1}\（类似DP思想，对于第\(b\个数，取或不取） \(C_{m+n}^n=C_m^0C_n^n+C_m^1C_n^{n-1}+...+C_m^nC_n^0\（从\(m\个数取\(n\个，\(n\个取0个开始遍历） \(C_n^m=C_n^{n-m}\（显然从\(n\中取\(m\个的方案数和从\(n\中取\(n-m\个的方案数是一样的）
（这些递推式还是挺容易证明的就不写了，敲公式好累）
(2 乘法原理和加法原理：类类独立，步步相关
\(n\类办法，在第一类办法中有\(m_1\种不同的方法，在第二类办法中有\(m_2\种不同的方法，……，在第\(n\类办法中有\(m_n\种不同的方法。那么完成这件事共有\(N=\sum_{i=1}^n m_i\种不同的方法。
\(m_1\种不同的方法，做第二步有m2种不同的方法，……，做第\(n\步有种\(m_n\不同的方法，那么完成这件事有\(N＝\prod_{i=1}^n m_i\种不同的方法。
(3 可重复元素的组合问题
从n个元素中，可重复的挑选m个元素组成集合，求：不同的集合有多少个？
\(C_{n+m-1}^m\
证明：隔板法。
∣∗∣∗∗∗∗∣∣∗∗∗∣∣∗∣（|是边界，*是球）
\(C_{n+m-1}^m\。 \(O(n^2\搞定了，俺觉得也可以一看wwww，部分dp表真是一个好东西啊。 https://blog.csdn.net/m0_37602827/article/details/100624871
3. 常用定理
(1 Lucas定理
结论：\(C_a^b \equiv C_{a\mod p}^{b \mod p}\times C_{a/p}^{b/p} (\mod p\ （\(p\为素数）
它还可以写成如下形式：
\(p\为素数，则\(n\的\(p\进制表示为\((a_k,a_{k-1},...,a_0\，\(m\的\(p\进制表示为\((b_k,b_{k-1},...,b_0\\(C_n^m\equiv C_{a_k}^{b_k}·C_{a_{k-1}}^{b_{k-1}}...C_{a_0}^{b_0} (\mod p\
很容易看出来，它就是形式一运用数学归纳法可以得出的结论。
证明： 引理1 \(C(p,x \equiv 0(\mod p, 0<x<p\
证明：$C(p,x\equiv \frac{p!}{x!(p-x!}\equiv \frac{p\times (p-1!}{x\times(x-1\times(p-x!} $
\(p\为素数，所以\(\forall x\in(0,p,(p,x=1\，故\(x|C_{p-1}^{x-1}\，则\(p|(\frac{p}{x}C_{p-1}^{x-1}\。 \(C(p,x \equiv p\times(x^{-1} \mod p\times C(p-1,x-1\equiv 0\mod p\引理2 \((1+x^p \equiv (1+x^p \mod p\\((1+x^p=\sum\limits _{k=0}^pC_p^kx^k\\(\sum\limits _{k=0}^pC_p^kx^k\equiv C(p,0x^0+C(p,px^p\equiv (1+x^p \mod p\
下面正式推导Lucas定理。
\(n=q_1p+r_1,m=q_2p+r_2\，则\(q_1=n/p,q_2=m/p\\((1+x^n\equiv (1+x^{q_1p+r_1}\equiv (1+x^{q_1p}\times(1+x^{r_1}\equiv [(1+x^p]^{q_1}\times(1+x^{r_1} \\ (1+x^p^{q_1}\times(1+x^{r_1} \equiv \sum\limits _{i=0}^{q_1}C(q_1,ix^{p\times i}\times \sum\limits _{j=0}^{r_1}C(r_1,jx^{j} (\mod p\\((1+x^n=\sum\limits _{i=0}^{n}C(n,ix^{i}\\(\therefore \sum\limits _{i=0}^{n}C(n,ix^{i}\equiv \sum\limits _{i=0}^{q_1}C(q_1,ix^{p\times i}\times \sum\limits _{j=0}^{r_1}C(r_1,jx^{j} (\mod p\\(C_n^m\为\((1+x^n\展开式中\(x^m\项前面的系数 \(\because m=q_2p+r_2,\therefore q_2=m/p,r_2=m-\lfloor \frac{m}{p} \rfloor \times p\\(C(n,mx^{m}\equiv C(q_1,q_2x^{p\times q_2}\times C(r_1,r_2x^{r_2} (\mod p\\(C_n^m\equiv C_{q_1}^{q_2}·C_{r_1}^{r_2} (\mod p\，得证。 推论1 \(C(n,m\为奇数的充要条件为，在二进制表示下（\(p=2\），\(\forall i\in[0,k],a_i\geq b_k\。 \(C(0,0=1,C(0,1=0,C(1,0=1,C(1,1=1\。 \(C(n,m\mod 2\，则对于\(n\上的为1的位\(a_i\，\(b_i\能取0或1，对于\(a_i=0\，则\(b_i\必须为0，得证。例题：HDU4349 Xiao Ming's Hope 结论就是\(2^{a_i=1的个数}\
(2 扩展Lucas定理
前置知识：卢卡斯定理 中国剩余定理
扩展Lucas定理用于求解以下公式：
\(C_a^b \mod p\，其中\(p\不一定是质数。 \(p\进行质因数分解，\(p=p_1^{a_1}\times p_2^{a_2}\times .. \times p_k^{a_k}\，显然\(\forall i,j \in [1,k], i\neq j, (p_i^{a_i},p_j^{a_j}=1\。
提高篇中已证明