54 lines
2.2 KiB
C++
54 lines
2.2 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
#define int long long
|
||
#define endl "\n"
|
||
const int N = 20, mod = 1e9 + 7;
|
||
|
||
int A[N];
|
||
int n, m;
|
||
|
||
// 快速幂
|
||
int qmi(int a, int k) {
|
||
int res = 1;
|
||
while (k) {
|
||
if (k & 1) res = res * a % mod;
|
||
a = a * a % mod;
|
||
k >>= 1;
|
||
}
|
||
return res;
|
||
}
|
||
|
||
int C(int a, int b) {
|
||
if (a < b) return 0;
|
||
int up = 1, down = 1;
|
||
for (int i = a; i > a - b; i--) up = i % mod * up % mod;
|
||
for (int i = 1; i <= n - 1; i++) down = i * down % mod; //(n-1)! % mod
|
||
down = qmi(down, mod - 2); // 费马小定理求逆元
|
||
|
||
return up * down % mod; // 费马小定理
|
||
}
|
||
|
||
signed main() {
|
||
cin >> n >> m;
|
||
for (int i = 0; i < n; i++) cin >> A[i]; // 第i个盒子中有A[i]枝花,限制条件
|
||
|
||
// yxc这里写的代码太随意了，把我直接干蒙圈了！
|
||
// 根据推导的式子，这里需要一个全部方案数=C(n + m - 1, n - 1)
|
||
// 也就是说 res的初始值就是上面的全部方案数。
|
||
// 可是，yxc大佬的大脑与正常人不一样，他居然没有给初始值，直接把初始值也写到下面的容斥原理代码中!!!
|
||
// 也就是所有限制条件全部不采用，也就是全部不受限制！也就是全部方案数！！！
|
||
int res = 0;
|
||
for (int i = 0; i < 1 << n; i++) { // 容斥原理的项数，0000 代表所有限制条件都不遵守,0001代表第1个限制条件遵守，其它3个不遵守
|
||
int sum = 0, cnt = 0; // 奇数个限制条件，需要减；偶数个限制条件，需要加。现在这种限制条件组合状态，是奇数个限制，还是偶数个限制？
|
||
for (int j = 0; j < n; j++) // 枚举状态的每一位
|
||
if (i >> j & 1) { // 如果此位是1
|
||
sum += A[j] + 1; // 拼公式
|
||
cnt++; // 限制条件个数,奇数个减，偶数个加
|
||
}
|
||
if (cnt & 1)
|
||
res = (res - C(m + n - 1 - sum, n - 1) + mod) % mod;
|
||
else
|
||
res = (res + C(m + n - 1 - sum, n - 1)) % mod;
|
||
}
|
||
cout << (res + mod) % mod << endl;
|
||
} |