博客

题意

n种小球放入m个不同的盒子中，要求在所有盒子中，包含n种小球

分析

我们知道m个盒子自由的组合，有



2

m

2^{m}







2











m













种

对于每种小球，我们要保证他存在，所以有



2

m

−

1

2^{m}-1







2











m












−








1





种

现在有n种小球，所以答案为:



(

2

m

−

1

)

n

(2^{m}-1)^{n}






(



2











m












−








1



)











n

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T>
void out(T x) { cout << x << endl; }
ll fast_pow(ll a, ll b, ll p) {ll c = 1; while(b) { if(b & 1) c = c * a % p; a = a * a % p; b >>= 1;} return c;}
ll exgcd(ll a, ll b, ll &x, ll &y) { if(!b) {x = 1; y = 0; return a; } ll gcd = exgcd(b, a % b, y, x); y-= a / b * x; return gcd; }
const ll mod = 1e9 + 7;
int main()
{
    ios::sync_with_stdio(false);
    ll n, m;
    cin >> n >> m;
    ll ans = (fast_pow(2, m, mod) - 1 + mod) % mod;
    ans = fast_pow(ans, n, mod) % mod;
    cout << ans << endl;
}