多重集组合
无限元素多重集组合
对于一个含有种元素的多重集,从当中取出个元素进行组合,共有
种取法,这个结论用隔板法易证:
有限元素多重集组合
对于一个含有种元素共计个的多重集,从当中取出 个元素进行组合,方案数为:
证明:如果没有数量限制那么答案显然是,但是由于数量有限,我们要排除多于的方案,令表示第种元素选了至少个的方案集合。要构造这样的方案,我们只需要先选出个该种元素,再在剩下的集合中选出个即可,于是我们有
所有所有不合法的方案可以表示为 接下来结合容斥原理易证。例子:CF451E
就是以上公式的应用,对于容斥原理使用递归的写法,求取组合数时使用了Lucas定理加以优化,代码很短:
#include <cstdio>
using namespace std;
typedef long long ll;
const ll P = 1000000007;
const int N = 22;
ll n, m, inv[N], a[N];
ll binom(ll a, ll b) {
if (a < 0 || b < 0 || a < b) return 0;
a %= P;
if (a == 0 || b == 0) return 1;
ll ret = 1;
for (ll i = a; i > a - b; i--)
ret = ret * i % P;
for (ll i = 1; i <= b; i++)
ret = ret * inv[i] % P;
return ret;
}
ll calc(int d, ll x) {
if (d == 0) return x == 0 ? 0 : binom(n + m - 1 - x, n - 1);
else return (calc(d - 1, x) - calc(d - 1, x + a[d] + 1)) % P;
}
void setup() {
inv[1] = 1;
for (int i = 2; i <= n; i++)
inv[i] = (-(P / i) * inv[P % i] % P + P) % P;
}
int main() {
scanf("%lld%lld", &n, &m);
setup();
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
ll ans = binom(n + m - 1, n - 1) + calc(n, 0);
printf("%lld\n", (ans % P + P) % P);
return 0;
}