a302: NOIP2011 Day2.1.计算系数

2021-06-06 16:07:59 +0800 CST Tags: combinatorics, number-theory, polynomial

出處：https://zerojudge.tw/ShowProblem?problemid=a302
提交：https://zerojudge.tw/Submissions?problemid=a302&account=allllllan123456

問題：給定一個多項式 $(ax+by)^k$，請求出它展開之後 $x^ny^{k-n}$ 項的係數，其中 $0\le n\le k\le 1000$、$0\le a, b\le 1000000$。因為這個係數可能很大，我們只想知道它對 10007 取餘數的结果。

解法：這題的精華不在於單純的公式計算，而是計算方法的技巧。我們都知道它的公式是 $C(k,n)\cdot a^n\cdot b^{k-n}$，而單純高次乘冪的計算 $a^n$ 和 $b^{k-n}$ 可以使用快速冪的技巧，至於組合數的部分有巴斯卡三角形或者是單純依賴階乘的算法，那因為這題需要 mod 10007，所以我們這邊採用後者，可以借助費馬小定理的力量把分母的階乘轉為分子的高次乘冪，更精確地來說：$\displaystyle C(k,n)\equiv\frac{k\cdot(k-1)\dots(k-n+1)}{n!}$$\displaystyle\equiv k\cdot(k-1)\dots(k-n+1)\cdot(n!)^{10005}\ (\text{mod}\ 10007)$。現在我們想進一步解釋為什麼 $(n!)^{-1}\equiv(n!)^{10005}\ (\text{mod}\ 10007)$ 是對的，根據費馬小定理：若 $p$ 是質數且 $a$、$p$ 互質，則 $a^{p-1}\equiv 1\ (\text{mod}\ p)$，而現在的 $p=10007$，並且 $a$ 只可能是由大於 0、不超過 1000 的整數們所構成 (乘起來)，於是 $a$ 和 $p$ 必互質，便可得到 $(n!)\cdot(n!)^{10005}\equiv 1\ (\text{mod}\ 10007)$ 的結論，也就是所求的 $(n!)^{10005}\equiv(n!)^{-1}$ 了。

 1#include <bits/stdc++.h>
 2using namespace std;
 3
 4// Ref: https://blog.csdn.net/qq_41709770/article/details/80957254
 5
 6const int mod = 10007;
 7
 8int fast_pow(int a, unsigned b) {
 9    int ans = 1; a %= mod;
10    while (b) {
11        if (b & 1) ans = ans * a % mod;
12        a = a * a % mod; b >>= 1;
13    }
14    return ans;
15}
16
17int C(int n, int m) {
18    int nu = 1, de = 1;
19    if (m > n/2) m = n - m;
20    for (int i=n; i>n-m; i--) nu = nu * i % mod;
21    for (int i=1; i<=m; i++) de = de * i % mod;
22    return nu * fast_pow(de, mod-2) % mod;
23}
24
25int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
26    int a, b, k, n, m;
27    cin >> a >> b >> k >> n >> m; // this problem promises (n + m == k)
28    cout << fast_pow(a,n) * fast_pow(b,m) % mod * C(k,n) % mod << '\n';
29    return 0;
30}