深圳建专业网站,互联网网站建设,移动网站有哪些,辽源市住房和城乡建设局网站【NOIP提高组】计算系数 C语言实现C实现Java实现Python实现 #x1f490;The Begin#x1f490;点点关注#xff0c;收藏不迷路#x1f490; 给定一个多项式 (ax by)^k #xff0c;请求出多项式展开后 x^n y^m 项的系数。
输入
共一行#xff0c;包含 5 个整数#x… 【NOIP提高组】计算系数 C语言实现C实现Java实现Python实现 The Begin点点关注收藏不迷路
给定一个多项式 (ax by)^k 请求出多项式展开后 x^n y^m 项的系数。
输入
共一行包含 5 个整数分别为 abknm每两个整数之间用一个空格隔开。
输出
输出共 1 行包含一个整数表示所求的系数这个系数可能很大输出对 10007 取 模后的结果。
样例输入
1 1 3 1 2样例输出
3提示
【数据范围】 对于 30%的数据有 0≤k≤10 对于 50%的数据有 a 1b 1 对于 100%的数据有 0≤k≤1,0000≤n, m≤k且 n m k0≤ab≤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点点关注收藏不迷路
