容斥原理

此处为笔记图片

例题：Devu和鲜花

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<iomanip>
#include<cstring>
#include<string>
#define LL long long

using namespace std;
const LL mod = 1e9 + 7;
LL n, m, a[25], ans;
LL dwn = 1;

long long read(){
	long long x=0,h=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')h=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*h;
}

LL power (LL a, LL b) {
	LL sum = 1;
	for ( ; b > 0; b >>= 1) {
		if (b & 1)sum = sum * a % mod;
		a = a * a % mod;
	}
	return sum;
}

LL inv (LL a) {
	return power(a, mod - 2) % mod;
}

LL C (LL N, LL M) {  // 注意数据类型！不是int
	if (N > M) return 0;
	if (M < 0) return 0;
	LL s = 1;
	for (LL i = M; i >= M - N + 1; i --) s *= (i % mod), /*处处取模好习惯！*/ s %= mod;
//	cout << "-" << s << endl;
	s = s * dwn % mod;
	return s % mod;
}

int main() {
	n = read(); m = read();
	for (int i = 1; i <= n; i ++) a[i] = read();
	for (int i = 1; i <= n - 1 ; i ++) dwn *= inv(i), dwn %= mod;  // C(n-1,*)中n-1不变，所以可以预处理，缩短时间
	
	for (LL i = 0; i <= (1 << n) - 1; i ++) {
		LL fh = 1, sum = 0, k = i;
		for (LL j = 1; k > 0; k >>= 1, j ++) {
			if (k & 1) {
				fh *= -1;
				sum += (a[j] + 1);
			}
		}
//		cout << sum << endl;
		ans += (C(n - 1, m - sum + n - 1) * fh + mod) % mod;  // 同下！
	}
	cout << ( ans + mod ) % mod << endl;  // 注意！此处需要防止ans是负的
	return 0;
}