【模板：求组合数】信息学奥赛一本通 1648：【例 1】「NOIP2011」计算系数 | 1866：【11NOIP提高组】计算系数 | 洛谷 P1313 [NOIP 2011 提高组] 计算系数

【题目链接】

ybt 1648：【例 1】「NOIP2011」计算系数
ybt 1866：【11NOIP提高组】计算系数
洛谷 P1313 [NOIP 2011 提高组] 计算系数
ybt 1648没有指明k kk的范围，在ybt 1866， 洛谷P1313中都以指明k ≤ 1000 k\le1000k≤1000

【题目考点】

1. 加法原理与乘法原理

加法原理：完成一件事的方法有n nn类，第i ii类包括m i m_imi​种不同的方法，而且这些方法不重合，则完成这件事共有N NN种方法，满足：N = m 1 + m 2 + ⋯ + m n N=m_1+m_2+⋯+m_nN=m1​+m2​+⋯+mn​。
口诀：分类相加
乘法原理：完成一件事需要n nn个步骤，其中第i ii个步骤有m i m_imi​种不同的完成方法，而且这些步骤互不干扰，则完成这件事共有N NN种方法，满足：N = m 1 m 2 ⋯ m n N=m_1m_2⋯m_nN=m1​m2​⋯mn​。
口诀：分步相乘

2. 排列组合

排列：从n nn个不同的元素中，取m ( m ≤ n ) m (m≤n)m(m≤n)个元素，按照一定顺序排成一列，称为从n nn个不同元素中取出m mm个元素的一个排列，这样的排列的个数称为排列数，记为P n m P_n^mPnm​或A n m A_n^mAnm​。P n n P_n^nPnn​称为n nn个元素的全排列。
P n m = n ( n − 1 ) . . . ( n − m + 1 ) = n ! ( n − m ) ! P_n^m=n(n-1)...(n-m+1)=\dfrac{n!}{(n-m)!}Pnm​=n(n−1)...(n−m+1)=(n−m)!n!​

第1步：从n nn个元素中取出一个元素，共n nn种取法。
第2步：从n − 1 n-1n−1个元素中取出一个元素，共n − 1 n-1n−1种取法。
…
第m mm步：从n − m + 1 n-m+1n−m+1个元素中取出一个元素，共n − m + 1 n-m+1n−m+1种取法。
根据乘法原理，有：P n m = n ( n − 1 ) . . . ( n − m + 1 ) P_n^m=n(n-1)...(n-m+1)Pnm​=n(n−1)...(n−m+1)

组合：从n nn个不同的元素中，取m ( m ≤ n ) m(m\le n)m(m≤n)个元素，组成一个集合，称为从n nn个不同元素中取出m mm个元素的一个组合，这样的组合的个数称为组合数，记为C n m C_n^mCnm​。

C n m = P n m P m m = n ( n − 1 ) . . . ( n − m + 1 ) m ( m − 1 ) . . . 1 = n ! ( n − m ) ! m ! C_n^m=\dfrac{P_n^m}{P_m^m}=\dfrac{n(n-1)...(n-m+1)}{m(m-1)...1}=\dfrac{n!}{(n-m)!m!}Cnm​=Pmm​Pnm​​=m(m−1)...1n(n−1)...(n−m+1)​=(n−m)!m!n!​

从n nn个元素中取出m mm个元素可以分为两步
第一步：从n nn个元素中取出m mm个元素的一个组合，方案数为C n m C_n^mCnm​
第二步：将这m mm个元素进行全排列，方案数为P m m P_m^mPmm​
根据乘法原理，有P n m = C n m P m m P_n^m=C_n^mP_m^mPnm​=Cnm​Pmm​
因此C n m = P n m P m m C_n^m=\frac{P_n^m}{P_m^m}Cnm​=Pmm​Pnm​​

C n m = C n n − m C_n^m=C_n^{n-m}Cnm​=Cnn−m​，一般用于简化计算过程。
特殊地：C n 0 = C n n = 1 C_n^0=C_n^n=1Cn0​=Cnn​=1。
当m > n m>nm>n时，不存在从n nn个数中取出m mm个数的方案，C n m = 0 C_n^m=0Cnm​=0

从n nn个元素中取出m mm个元素拿走，和在n nn个元素中取出n − m n-mn−m个元素留下的方案数是相同的。

杨辉恒等式：C n m = C n − 1 m + C n − 1 m − 1 C_n^m=C_{n-1}^{m}+C_{n-1}^{m-1}Cnm​=Cn−1m​+Cn−1m−1​

在n nn个元素中存在一个元素x xx。
如果不选择x xx，那么接下来要在剩下的n − 1 n-1n−1个元素中再选择m mm个元素，方案数为C n − 1 m C_{n-1}^{m}Cn−1m​
如果选择x xx，那么接下来要在剩下的n − 1 n-1n−1个元素中再选择m − 1 m-1m−1个元素，方案数为C n − 1 m − 1 C_{n-1}^{m-1}Cn−1m−1​
根据加法原理，有C n m = C n − 1 m + C n − 1 m − 1 C_n^m=C_{n-1}^{m}+C_{n-1}^{m-1}Cnm​=Cn−1m​+Cn−1m−1​

C n m = n m C n − 1 m − 1 C_n^m=\dfrac{n}{m}C_{n-1}^{m-1}Cnm​=mn​Cn−1m−1​

C n m = n ! ( n − m ) ! m ! = n m ( n − 1 ) ! ( n − m ) ! ( m − 1 ) ! = n m C n − 1 m − 1 C_n^m=\frac{n!}{(n-m)!m!}=\frac{n}{m}\frac{(n-1)!}{(n-m)!(m-1)!}=\frac{n}{m}C_{n-1}^{m-1}Cnm​=(n−m)!m!n!​=mn​(n−m)!(m−1)!(n−1)!​=mn​Cn−1m−1​

2. 二项式定理

( a + b ) n = ∑ i = 0 n C n i a i b n − i (a+b)^n =\sum\limits_{i=0}^nC_n^ia^ib^{n-i}(a+b)n=i=0∑n​Cni​aibn−i
或：
( a + b ) n = C n 0 a 0 b n + C n 1 a b n − 1 + . . . + C n n − 1 a n − 1 b + C n n a n b 0 (a+b)^n=C_n^0a^0b^{n}+C_n^1ab^{n-1}+...+C_n^{n-1}a^{n-1}b+C_n^na^nb^{0}(a+b)n=Cn0​a0bn+Cn1​abn−1+...+Cnn−1​an−1b+Cnn​anb0

每一个( a + b ) (a+b)(a+b)提供一个a aa或b bb
对于a i b n − i a^ib^{n-i}aibn−i项，需要在n nn个( a + b ) (a+b)(a+b)中选择i ii个( a + b ) (a+b)(a+b)提供a aa，另外n − i n-in−i个( a + b ) (a+b)(a+b)中提供b bb，共C n i C_n^iCni​种情况，根据加法原理，a i b n − i a^ib^{n-i}aibn−i项的系数为C n i C_n^iCni​。

【解题思路】

设M = 10007 M=10007M=10007，可以手写质数判断函数确定M MM为质数。
已知n + m = k n+m=kn+m=k，所以m = k − n m=k-nm=k−n
根据二项式定理，( a x + b y ) k (ax+by)^k(ax+by)k的x n y m x^ny^mxnym项为
C k n ( a x ) n ( b y ) k − n = C k n a n b k − n x n y k − n = C k n a n b m x n y m C_k^n(ax)^n(by)^{k-n}=C_k^na^nb^{k-n}x^ny^{k-n}=C_k^na^nb^mx^ny^mCkn​(ax)n(by)k−n=Ckn​anbk−nxnyk−n=Ckn​anbmxnym
因此该项的系数为C k n a n b m m o d M C_k^na^nb^m\bmod MCkn​anbmmodM。
可以使用快速幂求a n a^nan与b m b^mbm。
对于求组合数C k n C_k^nCkn​，有以下方法：

1. 求组合数数组

• 状态定义：设二维数组c，c[i][j]表示C i j C_i^jCij​。由于k ≤ 1000 k\le 1000k≤1000，所以数组的行数列数可以定为1005。
• 初始状态：C i 0 = 1 , i ∈ [ 0 , n ] C_i^0=1, i\in[0,n]Ci0​=1,i∈[0,n]，注意包括：C 0 0 = 1 C_0^0=1C00​=1
  由于结果要对M MM取模，我们求出的组合数也对M MM取模。
• 递推关系：C i j ≡ C i − 1 j + C i − 1 j − 1 ( m o d M ) C_i^j\equiv C_{i-1}^{j}+C_{i-1}^{j-1} \pmod MCij​≡Ci−1j​+Ci−1j−1​(modM)，其中j ∈ [ 1 , i ] j\in[1,i]j∈[1,i]

递推求出c数组，即可求出C n k C_n^kCnk​。
同样可以根据该原理写出记忆化递归算法。
该方法求C n m C_n^mCnm​，空间复杂度O ( n 2 ) O(n^2)O(n2)，时间复杂度：预处理O ( n 2 ) O(n^2)O(n2)，单次查询O ( 1 ) O(1)O(1)。

2. 使用阶乘公式

C n m ≡ n ! ( n − m ) ! m ! ( m o d M ) C_n^m\equiv \dfrac{n!}{(n-m)!m!}\pmod MCnm​≡(n−m)!m!n!​(modM)
设阶乘数组fac，fac[i]表示i ! i!i!。先预处理出1 ∼ k 1\sim k1∼k的阶乘。
设阶乘模M MM逆元的数组facInv，facInv[i]表示i ! − 1 m o d M i!^{-1}\bmod Mi!−1modM
先使用扩展欧几里得算法求出n ! − 1 m o d M n!^{-1}\bmod Mn!−1modM（由于M MM是质数，也可以使用快速幂求逆元）。
已知：i ! − 1 ≡ ( i + 1 ) − 1 ( i + 1 ) ( m o d M ) i!^{-1}\equiv (i+1)^{-1}(i+1)\pmod Mi!−1≡(i+1)−1(i+1)(modM)
而后使用该公式递推求出facInv数组。
C n m ≡ n ! ( n − m ) ! m ! ≡ n ! ( n − m ) ! − 1 m ! − 1 ( m o d M ) C_n^m\equiv \dfrac{n!}{(n-m)!m!}\equiv n!(n-m)!^{-1}m!^{-1}\pmod MCnm​≡(n−m)!m!n!​≡n!(n−m)!−1m!−1(modM)
fac[n]为n ! n!n!，facInv[n-1]为( n − m ) ! − 1 m o d M (n-m)!^{-1}\bmod M(n−m)!−1modM，facInv[m]为m ! − 1 m o d M m!^{-1}\bmod Mm!−1modM，可以通过该公式求出C n m C_n^mCnm​

该方法求C n m C_n^mCnm​，空间复杂度O ( n ) O(n)O(n)，时间复杂度：预处理O ( n ) O(n)O(n)，查询O ( 1 ) O(1)O(1).

3. 使用乘除计算公式

C n m ≡ n ( n − 1 ) . . . ( n − m + 1 ) m ( m − 1 ) . . . 1 ( m o d M ) C_n^m\equiv \dfrac{n(n-1)...(n-m+1)}{m(m-1)...1}\pmod MCnm​≡m(m−1)...1n(n−1)...(n−m+1)​(modM)
先求出m ! m o d M m!\bmod Mm!modM，再通过扩展欧几里得算法（模数为质数时可用快速幂）求出m ! − 1 m o d M m!^{-1}\bmod Mm!−1modM。
即C n m ≡ n ( n − 1 ) . . . ( n − m + 1 ) m ! − 1 ( m o d M ) C_n^m\equiv n(n-1)...(n-m+1)m!^{-1}\pmod MCnm​≡n(n−1)...(n−m+1)m!−1(modM)
该方法求C n m C_n^mCnm​，空间复杂度O ( 1 ) O(1)O(1)，时间复杂度：O ( m ) O(m)O(m)

【题解代码】

1. 求组合数数组

• 写法1：递推

#include<bits/stdc++.h>usingnamespacestd;constintN=1005,M=10007;typedeflonglongLL;LL a,b,k,n,m,c[N][N];//c[i][j]:组合数C(i, j)LLfastPow(LL a,LL b,LL m){LL r=1;while(b>0){if(b%2==1)r=r*a%m;a=a*a%m;b/=2;}returnr;}voidinitComb(LL n){for(inti=0;i<=n;++i)c[i][0]=1;for(inti=1;i<=n;++i)for(intj=1;j<=i;++j)c[i][j]=(c[i-1][j]+c[i-1][j-1])%M;}intmain(){cin>>a>>b>>k>>n>>m;initComb(k);cout<<fastPow(a,n,M)*fastPow(b,m,M)*c[k][n]%M;return0;}

• 写法2：记忆化递归

#include<bits/stdc++.h>usingnamespacestd;constintN=1005,M=10007;typedeflonglongLL;LL a,b,k,n,m,c[N][N];//c[i][j]:组合数C(i, j)LLfastPow(LL a,LL b,LL m){LL r=1;while(b>0){if(b%2==1)r=r*a%m;a=a*a%m;b/=2;}returnr;}LLcomb(LL n,LL m){if(m>n)return0;if(m==0)return1;if(c[n][m]>0)returnc[n][m];returnc[n][m]=(comb(n-1,m)+comb(n-1,m-1))%M;}intmain(){cin>>a>>b>>k>>n>>m;cout<<fastPow(a,n,M)*fastPow(b,m,M)*comb(k,n)%M;return0;}

2. 使用阶乘公式

#include<bits/stdc++.h>usingnamespacestd;constintN=1005,M=10007;typedeflonglongLL;LL a,b,k,n,m,fac[N],facInv[N];LLfastPow(LL a,LL b,LL m){LL r=1;while(b>0){if(b%2==1)r=r*a%m;a=a*a%m;b/=2;}returnr;}voidinitFac(LL n){fac[0]=1;for(inti=1;i<=n;++i)fac[i]=fac[i-1]*i%M;//fac[i]：i!facInv[n]=fastPow(fac[n],M-2,M);for(inti=n-1;i>=0;--i)//注意包括0facInv[i]=facInv[i+1]*(i+1)%M;//facInv[i]：i!^{-1} mod M}LLcomb(LL n,LL m){if(n<m)return0;returnfac[n]*facInv[n-m]%M*facInv[m]%M;}intmain(){cin>>a>>b>>k>>n>>m;initFac(k);cout<<fastPow(a,n,M)*fastPow(b,m,M)*comb(k,n)%M;return0;}

3. 使用乘除计算公式

#include<bits/stdc++.h>usingnamespacestd;constintN=1005,M=10007;typedeflonglongLL;LL a,b,k,n,m,fac[N],facInv[N];LLfastPow(LL a,LL b,LL m){LL r=1;while(b>0){if(b%2==1)r=r*a%m;a=a*a%m;b/=2;}returnr;}LLcomb(LL n,LL m){if(m>n)return0;LL fz=1,fm=1;for(inti=1;i<=m;++i){fz=fz*(n-i+1)%M;fm=fm*i%M;}returnfz*fastPow(fm,M-2,M)%M;}intmain(){cin>>a>>b>>k>>n>>m;cout<<fastPow(a,n,M)*fastPow(b,m,M)*comb(k,n)%M;return0;}