B. Alice and the List of Presents（组合数）

https://codeforces.com/contest/1236/problem/B

题意
给定 n 种小球，每种小球无数个。
一共 m 个盒子，每个盒子可以放若干种小球，但是每种小球只能放一个。
要求：

• m 个盒子中的所有小球必须为 n 种，也就是，n 种小球都要用到。
• 盒子可以为空。

问，一共有多少种放置方案？

$1\le n,m\le 10^9$

思路
如果从盒子的角度来看，考虑每个盒子装哪些种类的小球，那么最后还要考虑 n 种小球都要用到，要减去某种小球没有用到的方案，而哪些种小球又是问题。

但是如果反过来，考虑每种小球放到哪些盒子里，就很容易解决。
对于每种小球来说，每个盒子可放可不放，所以一共 $2^m$ 种情况，但是当前小球一定要用到，所以一共 $2^m-1$ 种情况。
而一共 n 种小球，所以总的方案数就为 $(2^m-1{)}^n$。

看思维能不能转变过来啊。

Code

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];

int qmi(int x, int y)
{
	int ans = 1;
	while(y)
	{
		if(y & 1) ans = ans * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return ans;
}

signed main(){
	Ios;
	
	cin >> n >> m;
	
	cout << qmi((qmi(2, m) - 1), n);
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30