目錄
前言
求法一
代碼
求法二
代碼
求法三
代碼
求法四
代碼
前言
今天要將最后一部分，主要涉及組合數的四種求法。
前置知識
組合數的通項公式：
組合數的遞推公式：
盧卡斯定理：
我們今天需要求的四種求法主要基于這幾個公式。
求法一
求法一利用的是遞推公式，主要用于n <= 2000即可以打n^2的表的題目。
這個遞推公式是怎樣求出來的呢？其實很簡單，我們單獨對一個元素做分類討論，顯然有兩種可能的情況：
-
選擇：
C_{n - 1}^{m - 1} -
不選擇：
C_{n - 1} ^ {m}
最后二者相加能夠得到的就是C_n^m，時間復雜度是O(n^2)。
代碼
const int N = 2010;
int C[N][N];
?
void init()
{for (int i = 0; i < N; i++){C[i][0] = 1; for (int j = 1; j <= i; j++)C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P;}
}求法二
求法二主要應對的是n <= 1e5這種只能夠打一維表的數據。我們使用通項公式求解。不過需要取模，而對于模意義下顯然不可以直接做除法，需要求逆元。
注意這里有個隱藏條件是P是質數，這樣才能保證每一項都存在逆元。時間復雜度為O(nlogn)
代碼
const int N = 100010, P = 10007;
int F[N], Fe[N];
?
int quick(int n, int k)
{int cnt = 1;while (k){if (k & 1) cnt = cnt * n % P;n = n * n % P;k >>= 1;}return cnt;
}
?
void init()
{F[0] = Fe[0] = 1;for (int i = 1; i < N; i++){F[i] = F[i - 1] * i % P;Fe[i] = Fe[i - 1] * quick(i, P - 2) % P;}
}求法三
可算是找到了一道模板題（
這道題可以發現n很大，若再使用階乘求得話時間復雜度就是nlogn是必定超時的。
對于這種情況我們就可以使用盧卡斯定理求解，當然依舊有個前提是P是質數。
至于這個盧卡斯定理怎么求出來的我也不太懂，大家記住就好了，很形象，不難記。
若使用盧卡斯定理的話時間復雜度是：
代碼
#include<iostream>
using namespace std;
const int P = 10007;
int t, m, n;
?
int quick(int n, int k)
{int cnt = 1;while(k){if(k & 1) cnt = cnt * n % P;k >>= 1;n = n * n % P;}return cnt;
}
?
int C(int n, int m)
{int l = 1;for(int i = 1, j = n; i <= m; i++, j--){l = l * j % P;l = l * quick(i, P - 2) % P; //乘以逆元}return l;
}
?
int lks(int n, int m)
{if(n < P) return C(n, m);return C(n % P, m % P) * lks(n/P, m/P) % P;
}
?
int main()
{scanf("%d", &t);while(t--){scanf("%d%d", &n, &m);printf("%d\n", lks(n, m));}}求法四
n很大并且不取余。
顯然對于這樣的問題就需要使用高精度來求解。
我們使用的依舊是通項公式。
不過對于通項公式：
里面是有乘法有除法的，這并不理想，有沒有更優秀的求法呢？
這個求法很巧妙的，原理就是將階乘分解質因數，然后消掉重復的部分，因為組合數都是整數所以上面部分是一定可以被下面部分整除的，所以大家不需要考慮消不完的情況。
那么我們如何對階乘分解質因數呢？這個很簡單，我們首先篩出所1~n中所有的質數，隨后運用一個公式：
對于這個公式主播最開始感覺有些摸不著頭腦，但是想明白后只想說：妙，太妙了……
如何來理解呢？其實很簡單n/p其實就是求出1 ~ n中能被p整除的數字的個數，以此類推……
代碼
#include<iostream>
#include<vector>
//#define int long long
using namespace std;
//typedef long long LL;
const int N = 1e6 + 10;
bool is_prime[N];
int n, m;
?
int quick(int n, int k)
{int l = 1;while (k){if (k & 1) l *= n;n = n * n;k >>= 1;}//printf("%d\n", l);return l;
}
?
vector<int> prime_shai(int n) //線性篩法
{vector<int> p;for (int i = 2; i <= n; i++){if (!is_prime[i]) p.push_back(i);for (int j = 0; p[j] <= n / i; j++){is_prime[i * p[j]] = true;if (i % p[j] == 0) break;}}return p;
}
?
int get_num(int n, int p)
{int l = 0;int cnt = p;while (n / p){l += n / p;p *= cnt;}return l;
}
?
vector<int> cur(vector<int>& A, int b)
{int x = 0;vector<int> C;for (int i = 0; i < A.size(); i++){x += A[i] * b;C.push_back(x % 10);x /= 10;}while (x){C.push_back(x % 10);x /= 10;}return C;
}
?
int main()
{scanf("%d%d", &n, &m);vector<int> A = { 1 }; //高精度vector<int> p = prime_shai(n);for (int i = 0; i < p.size(); i++){int l = get_num(n, p[i]) - get_num(m, p[i]) - get_num(n - m, p[i]);A = cur(A, quick(p[i], l));}for (int i = A.size() - 1; i >= 0; i--)printf("%d", A[i]);return 0;
}
