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;
}

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

文章作者:单林敏

发布时间:2019年10月18日 - 16:25:50

最后更新:2019年10月18日 - 16:34:31

原始链接:https://www.wolfdan.cn/codeforces593B-Alice-and-the-List-of-Presents-math-组合-思维-算法日常-36-100/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

-------------------本文结束 感谢您的阅读-------------------
0%