P5505 [JSOI2011]分特产（容斥多重集组合数）

思路:不难联想到是组合数学那一类题目偏多,给你m种球,每个有 a i a_i ai​个球,要求放入 n n n个盒子里面,求盒子中都有球的方案。 浓浓的组合数学味道,可惜我写的不多,滚去看题解了 考虑一下补集转换,先求允许空集的方案,再减去盒子中包含空盒的方案. 奉上笔记一页,供大家参考思路.

/*
Stairs upon the temple
I climb and I crawl in
People travel millions of miles just to see it
But they never conquer this way
*/
#include
using namespace std;
const int maxn = 1000+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector G[maxn];
ll mod = 1e9+7;
ll pw(ll a,ll b){
	ll ans = 1;a%=mod;
	while(b){
		if(b&1) ans=ans*a%mod;
		b>>=1;a=a*a%mod; 
	}
	return ans%mod;
}
ll inv(ll a){
	return pw(a,mod-2);
}
ll fac[maxn*2];
ll C(ll n,ll m){
	return fac[n]*inv(fac[m])%mod*inv(fac[n-m])%mod;
}
int a[maxn];
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	fac[0] =1;
	for(int i=1;i>n>>m;
	for(int i=1;i>a[i];
	ll ans = 0;
	for(int i=0;i