题目描述

难度分:$1500$

输入$n(1 \leq n \leq 10^9)$和$m(1 \leq m \leq 10^9)$。

有$n$种物品，每种物品有无数个。同一种物品都是相同的，无法区分。不同种类的物品都是不同的，可以区分。

选一些物品放入$m$个盒子。盒子都是不同的，可以区分。

要求：

1. 允许空盒。
2. 同一个盒子中，不能有相同的物品。
3. 每种物品都至少有一个装进某个盒子。

输出方案数。模$10^9+7$。

输入样例$1$

1 3

输出样例$1$

7

输入样例$2$

2 2

输出样例$2$

9

算法

数学

这种题目说难不难，说简单感觉有时候脑子转不过弯来也挺痛苦的。由于每一种球都不会出现在同一个盒子中两次，因此可以一种一种地来放每种球。首先是第$1$种球，如果选一个，那就要从$m$个盒子中选一个来放它，方案数为$C_{m}^{1}$；如果选两个，那就要从$m$个盒子中选两个来放两个第$1$种球，方案数为$C_{m}^{2}$，……，以此类推。根据二项式定理，第$1$种球的放法有$\Sigma_{i=1}^{m}C_{m}^{i}=2^m-1$，第一种球不可能选$m+1$个，否则根据鸽巢原理，一定存在一个盒子里面有两个第$1$种球。

接下来考虑第$2$种球到第$n$种球，每个都和第$1$种球的情况相同，方案数均为$2^m-1$。而每种球之间互相独立，所以乘法原理乘起来就可以了，答案为$(2^m-1)^n$，实现的时候用快速幂来求。

复杂度分析

时间复杂度

一共有两次快速幂，一次计算$2^m$，另一次计算$(2^m-1)^n$，时间复杂度为$O(log_2m+log_2n)$。

空间复杂度

仅使用了有限几个变量，额外空间复杂度为$O(1)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int MOD = 1e9 + 7;
int n, m;

int fast_power(int a, int k) {
    int res = 1;
    while(k) {
        if(k&1) res = (LL)res * a % MOD;
        a = (LL)a * a % MOD;
        k >>= 1;
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &m);
    printf("%d\n", fast_power((fast_power(2, m) - 1 + MOD)%MOD, n));
    return 0;
}