笔试时间：2024年09月18日 秋招

历史笔试传送门：2023秋招笔试合集

第一题

题目

小强是一个的农场主，农场里有n头牛，每头牛有着独一无二的体重，每一头牛的颜色可能是m种颜色其中的一种，小强带了一些牛（可能为0个）出来吃草。你需要回答出小强带出来的牛的组合—共有多少种可能？注意：因为每—头牛有自己的体重（没有两头牛体重相等），所以如果四头牛体重分别是1，2,3,4，颜色分別是y1,y1,y4,y4和另外一种方案：四头牛体重分别是1,2,3,4，颜色分别是y1,y4,y4,y1即使两个方案的颜色的种类对应的数量是相同的，但是因为颜色对应的体重不同所以是两个不同的方案。由于方案数可能很大，请对 1e9 + 7 取模。

输入描述

两个正整数n和m。

1 <= n <= 10^9, 1 <= m <= 10^9

输出描述

一个整数代表答案。

样例输入

3 2

样例输出

27

说明：

小强可能带0头牛出来，只有1种方案。

小强可能带1头牛出来，有3*2种方案（带出的是3头牛中的任意一个，这头牛的颜色可能为2种颜色之一）。

小强可能带2头牛出来，有3*2^2种方案。

小强可能带3头牛出来，有1*2^3种方案。

一共有1+6+12+8=27种方案。

参考题解

模拟计算，((1 + m)^n \mod (10^9 + 7))

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>

using namespace std;

const long long MOD = 1000000007;

int main() {
    long long n, m;
    cin >> n >> m;

    long long result = 1;
    long long base = (m + 1) % MOD;

    // 计算 (1 + m)^n % MOD
    while (n > 0) {
        if (n & 1) {
            result = (result * base) % MOD; // 乘以基数
        }
        base = (base * base) % MOD; // 基数平方
        n >>= 1; // n 右移一位
    }

    cout << result << endl;
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;

public class CowCombinations {
    private static final long MOD = 1000000007L;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong(); 
        long m = scanner.nextLong(); 
        scanner.close();

        long result = 1;
        long base = (m + 1) % MOD;

        // 计算 (1 + m)^n % MOD
        while (n > 0) {
            if ((n & 1) == 1) {
                result = (result * base) % MOD; // 乘以基数
            }
            base = (base * base) % MOD; // 基数平方
            n >>= 1; // n 右移一位
        }

        System.out.println(result);
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

MOD = 1000000007

def main():
    n = int(input())  # 读取n
    m = int(input())  # 读取m

    result = 1
    base = (m + 1) % MOD

    # 计算 (1 + m)^n % MOD
    while n > 0:
        if n & 1:
            result = (result * base) % MOD  # 乘以基数
        base = (base * base) % MOD  # 基数平方
        n >>= 1  # n 右移一位

    print(result)

if __name__ == "__main__":
    main()

第二题

题目

牛牛有n种糖果,每种糖果都有足够多,现在牛牛想用这些糖果组成一些糖果盒。每个糖果盒内放m个糖果。对于一个糖果盒,牛牛希望第i种糖果的数量不能少于l_i颗也不能多于r_i颗。满足条件的糖果盒组成方案可能会有很多,牛牛希望你帮他计算一共有多少种糖果盒的拼凑方案。对于两种方案，当有任意一种糖果个数不同，就视为两种不同方案。

输入描述

输入包括n+1行。

第一行包括两个正整数(1 <=n <= 20,1 <= m <= 100),表示糖果的种数和一盒糖果盒的糖果个数。

接下来的n行,每行两个整数l_i, r_i(0 <= l_i <= r_i<= 10),表示第i种糖果的数量限制上下限。

输出描述

输出一个整数,表示满足限定条件的方案数。保证答案在64位整数范围内。

样例输入

3 5

0 3

0 3

0 3

样例输出

12

参考题解

动态规划。定义状态：定义 dp[i][j] 表示前 i 种糖果中，可以凑成 j 个糖果盒的方案数。初始化：初始状态 dp[0][0] = 1，表示使用 0 种糖果凑成 0 个糖果盒只有 1 种方案，即不放糖果。其他 dp[0][j]（j > 0）应初始化为 0，因为用 0 种糖果无法凑成正数量的糖果盒。状态转移：dp[i][j] += dp[i-1][j-k]：如果用当前糖果的数量为 k，那前 i-1 种糖果凑成 j-k 个糖果盒的方案数就需要被加到 dp[i][j] 中。表示如果用第 i 种糖果放 k 颗糖果，则剩下的 j-k 个糖果盒的拼凑方案数是由前 i-1 种糖果决定的。对于第 i 种糖果，有 l[i-1] 到 r[i-1] 的数量限制。如果当前糖果的数量限制为 k，可以尝试将其放入糖果盒中，更新 dp[i][j]：最终 dp[n][m] 就是答案。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> l(n), r(n);
    for (int i = 0; i < n; i++) {
        cin >> l[i] >> r[i];
    }

    // 动态规划数组，dp[i][j] 表示前 i 种糖果凑成 j 个糖果盒的方案数
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, 0));

    dp[0][0] = 1;

    for (int i = 1; i <= n; i++) {  // 遍历每一种糖果
        for (int j = 0; j <= m; j++) {  // 遍历糖果盒内的糖果数量
            for (int k = l[i - 1]; k <= r[i - 1]; k++) {  // 当前糖果的可选数量
                if (j >= k) {
                    dp[i][j] += dp[i - 1][j - k];
                }
            }
        }
    }

    cout << dp[n][m] << endl;

    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); 
        int m = sc.nextInt();