题解 | 计算系数-NOIP2011提高组复赛
计算系数
https://ac.nowcoder.com/acm/contest/259/A
算法知识点: 组合数，二项式定理
复杂度： )
解题思路：
由二项式定理：
因此， 的系数是
。
时间复杂度分析:
计算的瓶颈在计算 上，对于分母中每个数都需要做一次快速幂，因此总时间复杂度是
。
C++ 代码：
#include <iostream>
#include <algorithm>
using namespace std; const int mod = 10007;
int qmi(int a, int k)
{
a %= mod;
int res = 1;
while (k)
{
if (k &1) res = res *a % mod;
a = a *a % mod;
k >>= 1;
}
return res;
}
int main()
{
int a, b, k, n, m;
cin >> a >> b >> k >> n >> m;
int res = qmi(a, n) *qmi(b, m) % mod;
for (int i = 1, j = k; i <= n; i++, j--)
{
res = res *j % mod;
res = res *qmi(i, mod - 2) % mod;
}
cout << res << endl;
return 0;
}