【代码】
#include <bits/stdc++.h>
#define For(i, a, b) for(register int i = (a); i <= (b); ++i)
#define Rof(i, a, b) for(register int i = (a); i >= (b); --i)
#define INF 0x3f3f3f3f
#define LL long long
#define Mod 1000000007
using namespace std;
int N;
LL A[21], M, Ans, Inv[21], Pos = 1;
LL Pow(LL a, int k) {
LL Ret = 1;
for(;k ; k >>= 1, a = a * a % Mod) if(k & 1) Ret = Ret * a % Mod;
return Ret;
}
LL C(LL x, int y) {
if(x < 0 || y < 0 || x < y) return 0;
if(x == y || y == 0) return 1;
x %= Mod;
LL Ret = 1;
For(i, 0, y - 1) Ret = Ret * (x - i) % Mod;
return Ret * Pos % Mod;
}
int main() {
scanf("%d%lld", &N, &M); For(i, 1, N) scanf("%lld", &A[i]);
For(i, 1, N - 1) Inv[i] = Pow(i, Mod - 2), Pos = Pos * Inv[i] % Mod;
Ans = C(N + M - 1, N - 1);
For(Sta, 1, Pow(2, N) - 1) {
LL t = 1, k = 0;
For(i, 1, N) if(Sta >> (i - 1) & 1) t += 1 + A[i], ++k;
if(k & 1) Ans = (Ans - C(N + M - t, N - 1)) % Mod;
else Ans = (Ans + C(N + M - t, N - 1)) % Mod;
}
printf("%lld\n", (Ans + Mod) % Mod);
return 0;
}
我不太懂这容斥为啥要找a[i] + 1 来进行容斥, 在不限制数量里面去重的情况下不应该是所有的情况都应该去重嘛。比如a[i] + 2 , a[i] + 3 ..... M
大佬,我有个地方没弄懂,组合数那里
为什么 x%=mod 后 这样做是对的 x-i不会使Ret变负的吗?