题解 | #礼物清单#

题目链接

礼物清单

题目描述

旺仔哥哥收到 $n$ 种不同的礼物（同种礼物彼此完全相同，数量无限）。他准备将礼物放入 $m$ 个贴有不同名字的盒子中寄给朋友。

打包需满足：

同一盒子内同一种礼物不能出现两次。
每一种礼物至少放入一个盒子（可以放入多个盒子）。

求满足要求的打包方案数量，对 $10^9+7$ 取模。

解题思路

这是一个组合计数问题。由于 $n$ 种礼物之间的打包决策是相互独立的，我们可以先分析一种礼物有多少种合法的打包方案，然后利用乘法原理推广到所有 $n$ 种礼物。

1. 单一礼物的打包方案

考虑其中任意一种礼物。我们有 $m$ 个不同的盒子。

对于盒子1，我们可以选择“放”或“不放”这种礼物，有 $2$ 种选择。
对于盒子2，同样有“放”或“不放” $2$ 种选择。
...
对于盒子m，也有 $2$ 种选择。

根据乘法原理，将这种礼物放入 $m$ 个盒子的总方案数（不考虑任何限制）为 $2 \cdot 2 \cdot \dots \cdot 2$ ( $m$ 次)，即 $2^m$ 种。这等价于为这种礼物选择一个盒子的子集（从空集到全集）进行放置。

现在，我们加入约束条件：“每一种礼物至少放入一个盒子”。

这意味着，对于我们正在考虑的这种礼物，它不能不被放入任何一个盒子。在上述 $2^m$ 种总方案中，只有一种方案是“所有盒子都不放”，即对应选择空集。我们需要排除掉这种不合法的方案。

因此，对于一种礼物，其合法的打包方案数量为 $2^m - 1$ 种。

2. 所有礼物的总打包方案

我们有 $n$ 种不同的礼物，且每种礼物的打包决策是独立的。

礼物1有 $2^m - 1$ 种合法方案。
礼物2有 $2^m - 1$ 种合法方案。
...
礼物n有 $2^m - 1$ 种合法方案。

根据乘法原理，将所有 $n$ 种礼物都按要求打包的总方案数，就是每种礼物合法方案数的乘积： $Total = (2^m - 1) \cdot (2^m - 1) \cdot \dots \cdot (2^m - 1)$ ( $n$ 次)

最终公式为： $ans = (2^m - 1)^n$ 。

3. 计算实现

由于 $n$ 和 $m$ 的值可能很大，直接计算会超出整数范围。因此，我们需要在模 $10^9+7$ 的意义下进行计算。整个计算过程需要用到两次快速幂（或称模幂）算法：

计算 $base = 2^m - 1 \pmod{10^9+7}$ 。
计算 $ans = base^n \pmod{10^9+7}$ 。

注意在计算 $2^m - 1$ 时，如果 $2^m \pmod P$ 的结果为 $0$ ，减一后会变成 $-1$ ，需要处理成 $P-1$ 。一个稳妥的写法是 (power(2, m) - 1 + MOD) % MOD。

代码

c++
java
python

#include <iostream>

using namespace std;

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

int main() {
    long long n, m;
    cin >> n >> m;
    
    long long mod = 1000000007;
    
    // 计算 2^m - 1
    long long base = (power(2, m) - 1 + mod) % mod;
    
    // 计算 (2^m - 1)^n
    long long ans = power(base, n);
    
    cout << ans << endl;
    
    return 0;
}

import java.util.Scanner;

public class Main {
    static final long MOD = 1000000007;

    public 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();
        
        // 计算 2^m - 1
        long base = (power(2, m) - 1 + MOD) % MOD;
        
        // 计算 (2^m - 1)^n
        long ans = power(base, n);
        
        System.out.println(ans);
    }
}

MOD = 1000000007

def power(base, exp):
    return pow(base, exp, MOD)

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

# 计算 2^m - 1
base = (power(2, m) - 1 + MOD) % MOD

# 计算 (2^m - 1)^n
ans = power(base, n)

print(ans)

算法及复杂度

算法：组合数学、快速幂（模幂）
时间复杂度：计算的核心是两次快速幂。计算 $2^m$ 的时间复杂度是 $\mathcal{O}(\log m)$ ，计算 $(2^m-1)^n$ 的时间复杂度是 $\mathcal{O}(\log n)$ 。因此，总时间复杂度为 $\mathcal{O}(\log m + \log n)$ 。
空间复杂度：算法只需要常数个变量来存储中间结果，因此总空间复杂度为 $\mathcal{O}(1)$ 。