【洛谷】P1313 [NOIP2011 提高组] 计算系数 的题解
【洛谷】P1313 [NOIP2011 提高组] 计算系数 的题解
题目传送门
题解
一题水水的数学题qaq，祝 CSP 初赛 rp++！！！
其实就是一个组合数加上杨辉三角（记得要快速幂），根据二项式定理， ( x + y ) k (x + y)^k (x+y)k 中 x m × y ( k − m ) x^m \times y^{(k - m)} xm×y(k−m) 的系数为 C ( k ， m ) C(k，m) C(k，m)。然后改造一下下得到 ( a x + b y ) k (ax + by)^k (ax+by)k 中 x m × y ( k − m ) x^m \times y^{(k - m)} xm×y(k−m) 的系数为 C ( k ， m ) × a m × b ( k − m ) C(k，m) \times a^m \times b^{(k - m)} C(k，m)×am×b(k−m)。最后在输出答案即可。
代码
#include <bits/stdc++.h>
#define lowbit(x) x & (-x)
#define endl "\n"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
namespace fastIO {inline int read() {register int x = 0, f = 1;register char c = getchar();while (c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f;}inline void write(int x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');return;}
}
using namespace fastIO;
int a, b, k, n, m;
int C[1005][1005];
int fast_pow(int a, int b) {int ans = 1;while (b) {if (b & 1) ans = (ans * a) % 10007;a = (a * a) % 10007;b >>= 1; }return ans;
}
int main() {//freopen(".in","r",stdin);//freopen(".out","w",stdout);a = read(), b = read(), k = read(), n = read(), m = read();a %= 10007; b %= 10007;a = fast_pow(a, n);b = fast_pow(b, m);for(int i = 1; i <= k; i ++) {C[i][0] = 1;C[i][i] = 1;}int p = min(n, m);for(int i = 2; i <= k; i ++) {for(int j = 1; j <= p; j ++) {C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % 10007;}}int ans = (a * b) % 10007;ans = (ans * C[k][p]) % 10007;write(ans);return 0;
}