P1313 计算系数
题目链接:https://www.luogu.org/problemnew/show/P1313
给定一个多项式(ax + by)^k,请求出多项式展开后x^n *y^m项的系数。
输入格式:
共一行,包含5个整数,分别为a ,b ,k ,n ,m每两个整数之间用一个空格隔开。
输出格式:
共1 行,包含一个整数,表示所求的系数,这个系数可能很大,输出对10007取模后的结果。
输入样例#1:
1 1 3 1 2输出样例#1:
3【数据范围】
对于30% 的数据,有0 ≤k ≤10;
对于50%的数据,有a = 1,b = 1;
对于100%的数据,有0≤k ≤1,000,0≤n, m≤k,且n+m=k ,0 ≤a,b ≤1,000,000。
noip2011提高组day2第1题
思路:二项式定理展开,用快速幂解决a^n *b^m,然后用杨辉三角的原理去计算组合数
代码:
#include<bits/stdc++.h> using namespace std; #define ll long long #define mod 10007 #define maxn 1000005 #define INF 0x3f3f3f3f #define N 3005 ll C[N][N]; void get_C(int n)//初始化杨辉三角 { C[0][0] = 1; for (int i = 1; i <= n; i++) { C[i][0] = 1; for (int j = 1; j <= i; j++) C[i][j] = (C[i - 1][j] % mod + C[i - 1][j - 1] % mod) % mod; //C[i][j] = (C[i-1][j]+C[i-1][j-1])%MOD; } } ll quickpow(ll a, ll b, ll n)//快速幂 { if (b == 1)return a; else { if (b % 2 == 0) { ll t = quickpow(a, b / 2, n); return t * t%n; } else { ll t = quickpow(a, b / 2, n); t = t * t%n; return t * a%n; } } } int main() { get_C(3000); ll a, b, k, n, m; cin >> a >> b >> k >> n >> m; //cout << quickpow(a, n, mod) << " " << quickpow(b, m, mod) << " " << C[k][n] % mod << endl; cout << ((quickpow(a, n, mod)*quickpow(b, m, mod)) % mod*C[k][n] % mod) % mod<<endl; //cout << C[1000][500]; } //829231 1000000 1000 500 500 //6880