題意
有n種物品和m個背包，每種物品有無限個，現將若干個物品放到這些背包中，滿足：
1、每個背包里不能出現相同種類的物品（允許有空背包）；
2、在所有的m個背包中，每種物品都出現過，
求方案數，對10^9+7取模，
思路
考慮每個物品在每個背包是否出現，那么對于物品i，有2^m中方案，然后因為在所有背包中每種物品至少要出現一次，所以要減去全不出現的方案，所以是2^m - 1，有n個物品，那么就是（2^m -1）^n
代碼
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=200005;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qpow(ll a,ll b){ll res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll inv(ll a,ll p){return qpow(a,p-2);}
int main()
{
std::ios::sync_with_stdio(false);
ll n,m;
cin>>n>>m;
cout<<qpow((qpow(2,m)-1+mod)%mod,n)<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/122735.html
標籤：其他