【NOIP提高组】计算系数

💐The Begin💐点点关注，收藏不迷路💐

给定一个多项式 (ax + by)^k ，请求出多项式展开后 x^n y^m 项的系数。

输入

共一行，包含 5 个整数，分别为 a，b，k，n，m，每两个整数之间用一个空格隔开。

输出

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

样例输入

1 1 3 1 2

样例输出

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。

C语言实现

#include <stdio.h>
#include <stdlib.h>// 定义常量
#define N 1010
#define MOD 10007// 二维数组用于存储组合数
int c[N][N];// 输入参数
int a, b, k, n, m;// 快速幂函数，用于计算a的b次幂对MOD取模的结果
int qmi(int a, int b) {a %= MOD;int res = 1;while (b) {if (b & 1) {res = res * a % MOD;}b >>= 1;a = a * a % MOD;}return res;
}int main() {// 读取输入参数scanf("%d %d %d %d %d", &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] + c[i - 1][j - 1]) % MOD;}}}// 根据二项式定理计算并输出结果int coefficient = c[k][n] * qmi(a, n) % MOD * qmi(b, m) % MOD;printf("%d\n", coefficient);return 0;
}

C++实现

#include <iostream>
#include <algorithm>// 定义常量
const int N = 1010;
const int MOD = 10007;// 二维数组用于存储组合数
int c[N][N];// 输入参数
int a, b, k, n, m;// 快速幂函数，用于计算a的b次幂对MOD取模的结果
int qmi(int a, int b) {a %= MOD;int res = 1;while (b) {if (b & 1) {res = res * a % MOD;}b >>= 1;a = a * a % MOD;}return res;
}int main() {// 读取输入参数std::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] + c[i - 1][j - 1]) % MOD;}}}// 根据二项式定理计算并输出结果int coefficient = c[k][n] * qmi(a, n) % MOD * qmi(b, m) % MOD;std::cout << coefficient << std::endl;return 0;
}

Java实现

import java.util.Scanner;public class Main {// 定义常量static final int N = 1010;static final int MOD = 10007;// 二维数组用于存储组合数static int[][] c = new int[N][N];// 输入参数static int a, b, k, n, m;// 快速幂函数，用于计算a的b次幂对MOD取模的结果static int qmi(int a, int b) {a %= MOD;int res = 1;while (b!= 0) {if ((b & 1)!= 0) {res = res * a % MOD;}b >>= 1;a = a * a % MOD;}return res;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取输入参数a = scanner.nextInt();b = scanner.nextInt();k = scanner.nextInt();n = scanner.nextInt();m = scanner.nextInt();// 预处理组合数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] + c[i - 1][j - 1]) % MOD;}}}// 根据二项式定理计算并输出结果int coefficient = c[k][n] * qmi(a, n) % MOD * qmi(b, m) % MOD;System.out.println(coefficient);}
}

Python实现

# 定义常量
N = 1010
MOD = 10007# 输入参数
a, b, k, n, m = map(int, input().split())# 二维列表用于存储组合数（初始化为全0）
c = [[0] * (N) for _ in range(N)]# 快速幂函数，用于计算a的b次幂对MOD取模的结果
def qmi(a, b):a %= MODres = 1while b:if b & 1:res = res * a % MODb >>= 1a = a * a % MODreturn res# 预处理组合数
for i in range(k + 1):for j in range(i + 1):if j == 0:c[i][j] = 1else:c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD# 根据二项式定理计算并输出结果
coefficient = c[k][n] * qmi(a, n) % MOD * qmi(b, m) % MOD
print(coefficient)

💐The End💐点点关注，收藏不迷路💐