洛谷题单指南-组合数学与计数-P1313 [NOIP 2011 提高组] 计算系数

原题链接：https://www.luogu.com.cn/problem/P1313

题意解读：计算多项式展开后某项的系数。

解题思路：二项式定理的裸题。

根据二项式定理：

(by+ax)^k中有一项是C(k,m)(by)^m(ax)ⁿ，因此xⁿy^m的系数为C(k,m)b^maⁿ

用组合数和快速幂求解即可。

100分代码：

#include <bits/stdc++.h>
using namespace std;const int N = 1005, MOD = 10007;
int c[N][N];
int a, b, k, n, m;int ksm(int a, int b, int mod)
{int res = 1;while(b){if(b & 1) res = 1ll * res * a % mod;a = 1ll * a * a % mod;b >>= 1;}return res;
}int main()
{cin >> a >> b >> k >> n >> m;//组合数初始化for(int i = 0; i <= k; i++){for(int j = 0; j <= i; j++){if(j == 0) c[i][j] = 1;else c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;}}int ans = c[k][m] * ksm(b, m, MOD) % MOD * ksm(a, n, MOD) % MOD;cout << ans;return 0;
}