Contents

codeforces593B.Alice and the List of Presents_math_组合_思维_算法日常[36/100]

题目链接

codeforces593B.Alice and the List of Presents

题意

  • n种礼物,每种无限个
  • 然后m个朋友对应m个盒子
  • 每个盒子中的每种礼物最多一个
  • 每种礼物都应该被放置出去至少一个
  • 求放置的方法数量

题解

  • 考虑每种礼物(共有n种)的放置方式,有m个盒子,tp = C(n 1)+C(n 2)+…+C(n n) = 2^n - 1
  • 然后总共有n种,所以选择n次,也就是tp^n

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for(int i = int(a); i <= int(b); ++i)
#define per(i, b, a) for(int i = int(b); i >= int(a); --i)
#define mem(x, y) memset(x, y, sizeof(x))
#define SZ(x) x.size()
#define mk make_pair
#define pb push_back
#define fi first
#define se second
const ll mod=1000000007;
const int inf = 0x3f3f3f3f;
inline int rd(){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f;}
inline ll qpow(ll a,ll b){ll ans=1%mod;for(;b;b>>=1){if(b&1)ans=ans*a%mod;a=a*a%mod;}return ans;}
int n,m;

int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    cout<<qpow(qpow(2,m)-1,n)<<endl;

    return 0;
}