自学内容网 自学内容网

【NOIP提高组】计算系数

【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 %= MOD
    res = 1
    while b:
        if b & 1:
            res = res * a % MOD
        b >>= 1
        a = a * a % MOD
    return res


# 预处理组合数
for i in range(k + 1):
    for j in range(i + 1):
        if j == 0:
            c[i][j] = 1
        else:
            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💐点点关注,收藏不迷路💐

原文地址:https://blog.csdn.net/qq_41840843/article/details/143668773

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!