首页 > 分享 > 【容斥原理】Devu和鲜花

【容斥原理】Devu和鲜花

花匠小妙招
2024-11-11 09:23

Devu 有 N 个盒子，第 i 个盒子中有 Ai 枝花。
同一个盒子内的花颜色相同，不同盒子内的花颜色不同。
Devu 要从这些盒子中选出 M 枝花组成一束，求共有多少种方案。
若两束花每种颜色的花的数量都相同，则认为这两束花是相同的方案。
结果需对 109+7 取模之后方可输出。

题目链接：https://www.acwing.com/problem/content/216/

转化题目要求，也就是每个盒子都有 a i a_i ai个花，想要从 n n n个盒子中每个都任意选出 x i x_i xi个，组出 m m m，也就是：
x 1 + x 2 + x 3 + . . . + x n = m + n x_1 + x_2 + x_3+...+x_n = m + n x1+x2+x3+...+xn=m+n
每个 x i x_i xi可以为 0 0 0，这个我们并不擅长，于是我们加上 n n n ，那么也就是，总共有 n n n个不为 0 0 0的盒子，我们要每个盒子挑出一部分，加起来和为 m + n m + n m+n个，这个我们十分擅长，用隔板法即可，答案为 C m + n − 1 k − 1 C_{m + n - 1}^ {k -1 } Cm+n−1k−1
但是题目并没有那么简单，我们仍需满足
∀ x i ≤ a i forall x_i le a_i ∀xi≤ai
我们发现这个并不好构造，于是我们考虑反面，如果每一个盒子都可以随意挑，没有任何限制 ,那么答案是
C m + n − 1 n − 1 C_{m + n - 1}^ {n -1 } Cm+n−1n−1
这样，减去不满足的即可，这时用到容斥原理。
那么，我们该如何考虑他的反面呢？答案是，只要有一个 x i x_i xi超过 a i a_i ai即可，也就是
∃ x i ≥ a i + 1 exist x_i ge a_i + 1 ∃xi≥ai+1
这时候考虑容斥原理，我们假设第一个事件（ x i ≥ a i + 1 x_ i ge a_i + 1 xi≥ai+1）为 s i s_i si
那么答案为：
C m + k − 1 k − 1 − ∣ s 1 ∪ s 2 ∪ . . . ∪ s n ∣ 这时候就可以以容斥原理展开 C m + k − 1 k − 1 − ∣ s 1 ∣ − ∣ s 2 ∣ − ∣ s 3 ∣ − ∣ s 4 ∣ . . . + ∣ s 1 ∩ s 2 ∣ + ∣ s 1 ∩ s 3 ∣ + . . . e n d C_{m + k - 1}^ {k -1 } - |s_1 cup s_2 cup...cup s_n|\ 这时候就可以以容斥原理展开\ C_{m + k - 1}^ {k -1 } - |s_1| - |s_2| - |s_3| - |s_4|... + |s_1 cap s_2| + |s_1cap s_3| + ...\ end Cm+k−1k−1−∣s1∪s2∪...∪sn∣这时候就可以以容斥原理展开Cm+k−1k−1−∣s1∣−∣s2∣−∣s3∣−∣s4∣...+∣s1∩s2∣+∣s1∩s3∣+...end
柿子推完，不代表题目已经完了，这里我们还要思考一个问题： s i s_i si怎么求？
首先，我们在明确一下 s i s_i si的定义：即，在第 i i i个物品中取出至少 a i + 1 a_i + 1 ai+1个物品
以 s i s_i si举例子，我们总共有 m + n m + n m+n个,现在要取走至少 a i + 1 a_i + 1 ai+1个，剩下 m + n − ( a i + 1 ) m + n - (a_i + 1) m+n−(ai+1)个，那么其他还是随意取，我们就用隔板法，也就是留 a i + 1 a_i + 1 ai+1个物品，给我们的第 i i i个物品，那么其他还是随便取，我们再用隔板法，就能算出这种情况下的答案： C m + n − 1 − ( a i + 1 ) n − 1 C_{m + n - 1 - (a_i + 1)}^{n - 1} Cm+n−1−(ai+1)n−1,如果两个物品都大于等于 a i + 1 a_i + 1 ai+1，那么答案为： C m + n − 1 − ( a i + 1 ) − ( a i ′ + 1 ) n − 1 C_{m + n - 1 - (a_i + 1) - (a_{i'}+ 1)}^{n - 1} Cm+n−1−(ai+1)−(ai′+1)n−1

那么考虑每个物品的枚举方法，因为物品数，很小，我们可以用二进制枚举，枚举的方案数为 2 n 2^n 2n,算组合数我们用最朴素的方式，时间复杂度大概是: O ( 2 n ∗ n ) O(2^n*n) O(2n∗n)

#include <bits/stdc++.h> #define rep(i , a , b) for(int i = (a);i <= (b);i ++) using namespace std; typedef long long LL; const int N = 30; const int p = 1e9 + 7; const int mod = 1e9 + 7; LL n , m , a[N] , inn = 1; LL qmi(LL a , LL b) { a = a % p; LL res = 1; while(b) { if(b & 1) res = res * a % p; a = a * a % p; b >>= 1; } return res; } LL C(LL a, LL b) { if (a < b) return 0; LL up = 1; for (LL i = 1 , j = a;i <= b;i ++ , j --) up = j % p * up % p; return up * inn % p; } int main() { LL res = 0; scanf("%lld %lld" , &n , &m); rep (i , 0 , n - 1) scanf("%lld" , &a[i]); rep (i , 1 , n - 1) inn = inn * i % p; inn = qmi(inn , p - 2); rep (i , 0 , (1 << n) - 1) { LL s = m + n - 1; int sign = 1; rep(j , 0 , n - 1) if(i >> j & 1) s -= (a[j] + 1), sign *= -1; res = (res % p + sign * C(s , n - 1) % p) % p; } printf("%lldn" , (res % p + p) % p); return 0; }

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647 参考资料:

https://www.acwing.com/solution/content/13666/