【NOIP提高组】计算系数

给定一个多项式 (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)