【题目链接】
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=m1m2⋯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=PmmPnm=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=CnmPmm
因此C n m = P n m P m m C_n^m=\frac{P_n^m}{P_m^m}Cnm=PmmPnm
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=mnCn−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)!=mnCn−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∑nCniaibn−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=Cn0a0bn+Cn1abn−1+...+Cnn−1an−1b+Cnnanb0
每一个( 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=Cknanbk−nxnyk−n=Cknanbmxnym
因此该项的系数为C k n a n b m m o d M C_k^na^nb^m\bmod MCknanbmmodM。
可以使用快速幂求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;}
