计算系数（多项式展开+快速幂）

计算系数

时间限制: 1 Sec  内存限制: 128 MB

题目描述

给定一个多项式(by+ax)k，请求出多项式展开后xn * ym 项的系数。

输入

共一行，包含5 个整数，分别为 a ，b ，k ，n ，m，每两个整数之间用一个空格隔开。0≤k≤1000, 0≤n,m≤k 且 n+m=k, 0≤a,b≤100,000

输出

输出共1 行，包含一个整数，表示所求的系数，这个系数可能很大，输出对10007 取模后的结果。

样例输入

复制样例数据

1 1 3 1 2

样例输出

3

饿，最近快速幂写的贼多。

=,所以要求的即i=m,所以系数为,快速幂求一下就好了

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

const int mod = 10007;

int a, b, k, n, m;

int pow_c(int x, int num){
	int res = 1 % mod;
	x %= mod;
	while(num){
		if(num & 1) res = (res * x) % mod;
		x = (x * x) % mod;
		num >>= 1;
	}
	return res;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d %d %d %d %d", &a, &b, &k, &n, &m);
	int c[k + 1];
	c[1] = 1;
	for (int i = 2; i <= k; i++) c[i] = c[i - 1] * i % mod;
	int ans = c[k] * pow_c(c[m] * c[k - m], mod - 2) % mod;
	printf("%d\n", ans * pow_c(b, k - n) % mod * pow_c(a, n) % mod);

	return 0;
}
/**/