题解 | #礼物清单#

题目链接

礼物清单

题目描述

有 $N$ 种不同的礼物和 $M$ 个不同的盒子。每种礼物的数量都是无限的。现在需要将这些礼物打包，并满足以下条件：

同一个盒子内，同一种礼物不能出现两次（即对于一种礼物，一个盒子要么不放，要么只放一个）。
每一种礼物至少要被放入一个盒子中。

求满足要求的打包方案总数，结果对 $1,000,000,007$ 取模。

输入:

一行输入两个整数 $N, M$ ，分别表示礼物种类数与盒子数。

输出:

输出一个整数，表示方案数量模 $1,000,000,007$ 的值。

解题思路

这个问题的核心思想是分步决策和乘法原理。我们可以先考虑一种礼物有多少种放法，然后将问题推广到 $N$ 种礼物。

分析一种礼物的放置方案
- 假设我们只考虑第1种礼物。我们有 $M$ 个不同的盒子。
- 对于第一个盒子，我们可以选择放或不放这种礼物，有2种选择。
- 对于第二个盒子，同样有2种选择。
- ...
- 对于第 $M$ 个盒子，依然有2种选择。
- 根据乘法原理，对于这一种礼物，总共有 $2 \cdot 2 \cdot \dots \cdot 2$ ( $M$ 次) = $2^M$ 种放置方式。
- 然而，题目要求“每一种礼物至少要被放入一个盒子中”。这意味着我们必须排除掉“这种礼物一个盒子都没放”的情况。
- “一个盒子都没放”只有一种情况（即所有盒子都选择“不放”）。
- 所以，对于单独一种礼物，满足条件的放置方案有 $2^M - 1$ 种。
推广到 $N$ 种礼物
- 我们有 $N$ 种不同的礼物。
- 第1种礼物的放置方案有 $2^M - 1$ 种。
- 第2种礼物的放置方案也有 $2^M - 1$ 种。
- ...
- 第 $N$ 种礼物的放置方案同样有 $2^M - 1$ 种。
- 由于每种礼物的放置方式是相互独立的，再次根据乘法原理，总的方案数就是将每种礼物的方案数相乘。
- 总方案数 = $(2^M - 1) \cdot (2^M - 1) \cdot \dots \cdot (2^M - 1)$ ( $N$ 次) = $(2^M - 1)^N$
计算
- 由于 $N$ 和 $M$ 的值可能很大，直接计算会超出整数范围，因此我们需要使用快速幂算法来处理幂运算，并在每一步都进行取模。
- 最终的计算公式为： power( (power(2, M) - 1), N ) 其中 power 是快速幂函数，所有计算都在模 $1,000,000,007$ 下进行。
- 注意在计算 (power(2, M) - 1) 时，为防止结果为负，应写成 (power(2, M) - 1 + MOD) % MOD。

代码

cpp
java
python

#include <iostream>

using namespace std;
using LL = long long;

const int MOD = 1e9 + 7;

LL power(LL base, LL exp) {
    LL res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    LL n, m;
    cin >> n >> m;

    LL ways_for_one_gift = (power(2, m) - 1 + MOD) % MOD;
    LL total_ways = power(ways_for_one_gift, n);

    cout << total_ways << '\n';

    return 0;
}

import java.util.Scanner;

public class Main {
    static final int MOD = 1_000_000_007;

    static long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) {
                res = (res * base) % MOD;
            }
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }

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

        long waysForOneGift = (power(2, m) - 1 + MOD) % MOD;
        long totalWays = power(waysForOneGift, n);

        System.out.println(totalWays);
    }
}

MOD = 1_000_000_007

n, m = map(int, input().split())

# Python 内置的 pow(base, exp, mod) 效率很高
ways_for_one_gift = (pow(2, m, MOD) - 1 + MOD) % MOD
total_ways = pow(ways_for_one_gift, n, MOD)

print(total_ways)

算法及复杂度

算法：数学、乘法原理、快速幂
时间复杂度： $\mathcal{O}(\log M + \log N)$ ，来自两次快速幂的计算。
空间复杂度： $\mathcal{O}(1)$ 。