同程旅行笔试同程旅行笔试题 0924

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

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

第一题

题目：小红的方案数

小红想构造一个长n宽m的数组，满足第奇数个元素都是奇数，第偶数个元素都是偶数（即n和m的奇偶性相同，数组下标从1开始计算）。且每个元素都在[1, m]之间。小红想知道一共有多少种不同的方案？答案请对10^9 + 7取模。

输入描述

第一行两个正整数n, m。

输出描述

输出一个数，代表构造的方案数。

样例输入

3 3

样例输出

6

参考题解

我们需要计算长度为n的数组中，奇数位置和偶数位置的元素各自有多少种选择，然后将这些选择相乘得到总的方案数。

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

#include <iostream>
using namespace std;

const int MOD = 1000000007;

long fastPow(long base, long exponent) {
    long result = 1;
    while (exponent > 0) {
        if (exponent & 1) {
            result = (result * base) % MOD;
        }
        base = (base * base) % MOD;
        exponent >>= 1;
    }
    return result;
}

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

    long oddCount = (n + 1) / 2;
    long evenCount = n / 2;
    long oddChoices = (m + 1) / 2;
    long evenChoices = m / 2;

    long oddResult = fastPow(oddChoices, oddCount);
    long evenResult = fastPow(evenChoices, evenCount);

    long result = (oddResult * evenResult) % MOD;
    cout << result << endl;

    return 0;
}

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

import java.util.Scanner;

public class Main {
    private  static  final int MOD =1000000007;
 public static void main(String[] args) {
   
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int m = scanner.nextInt();
    scanner.close();

    long oddCount = (n + 1) / 2;
    long evenCount = n / 2;
    long oddChoices = (m + 1) / 2;
    long evenChoices = m / 2;

    long oddResult = fastPow(oddChoices, oddCount);
    long evenResult = fastPow(evenChoices, evenCount);

    long result = (oddResult * evenResult) % MOD;
    System.out.println(result);
}

private static long fastPow(long base, long exponent) {
    long result = 1;
    while (exponent > 0) {
        if ((exponent & 1) == 1) {
            result = (result * base) % MOD;
        }
        base = (base * base) % MOD;
        exponent >>= 1;
    }
    return result;
  }
}

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

MOD = 1000000007

def fast_pow(base, exponent):
    result = 1
    while exponent > 0:
        if exponent & 1:
            result = (result * base) % MOD
        base = (base * base) % MOD
        exponent >>= 1
    return result

if __name__ == "__main__":
    n, m = map(int, input().split())

    odd_count = (n + 1) // 2
    even_count = n // 2
    odd_choices = (m + 1) // 2
    even_choices = m // 2

    odd_result = fast_pow(odd_choices, odd_count)
    even_result = fast_pow(even_choices, even_count)

    result = (odd_result * even_result) % MOD
    print(result)