题目链接：题目
大概题意：有一个大集合S，里面有n（≤231-1）个元素，现在从中任意选出k（≤231-1）个子集组成一个有序集合对（S1，S2.....Sk），问其中有多少个集合对满足所有选出的子集的交集为空（S1 ∩ S2 .....Sk = Φ)
做法：
先说句废话。
首先要注意的是题目说所有的子集的交集为空集，不代表某两个子集之间交集一定为空。甚至有可能任意两个子集之间交集都不为空，但是所有子集之间的交集为空。
我当时想到这一点之后，就开始用排除法。即用全部减去不符合要求的。然后开始了漫长的推公式。。。。。。
推半天推不出来，上网看题解。发现是恶心的容斥原理。。。
题解一
（容斥原理不懂的同学可以跳过这一部分）
首先方案总数为（2^n）^k
所有子集的交集至少含一个元素的方案C（n，1）*（2^（n-1））^k
所以答案就是（2^n）^k-C（n，1）*（2^（n-1））^k，哈哈，这题真简单，要什么容斥原理。。。。
错！！！！！！！！
我当时也是这么想的，结果发现——————
交集只含一个元素的方案被减掉了，但是交集只含两个元素的方案被减了两次！
于是我们加多一项，变成了
（2^n）^k-C（n，1）*（2^（n-1））^k+C（n，2）*（2^（n-2））^k
但是仔细再想想，不对，那交集只含三个元素的方案发生了什么。。。
事实上，交集只含三个元素的方案被减了C(3，1)次，又被加上了C(3，2）次，所以还要减去一次，即变成
（2^n）^k-C（n，1）*（2^（n-1））^k+C（n，2）*（2^（n-2））^k-C（n，3）*（2^（n-3））
然后。。。。
是的，你猜对了，最后这条式子会变成这样的庞然大物：
（2^n）^k-C（n，1）*（2^（n-1））^k+C（n，2）*（2^（n-2））^k-C（n，3）*（2^（n-3））....
+(-1)^t*C（n，t）*（2^（n-t））^k........+(-1)^n*C（n，n）*（2^（n-n））^k
再然后，把这条式看成是类似（a+b）^n展开式的形式，整合得到（2^k-1）^n
再然后套个快速幂取模就行了。。。
总结：这种方法还是很有启发性的，除了式子庞大，极费脑力，考试时绝对推不出来就是了。
题解二：
在和albertxwz的交流中，我发现了思想的闪光。
下面无耻的抄袭下他的简洁思想：
对于大集合每一个元素x，每个子集Si要么包含它，要么不包含它。也就是两种可能。
所以元素x在所有子集中的情况可以统计出来：2^k
但是所有子集不能都包含元素x，否则就不符合条件了，所以还要减1：2^k-1
总共有n个元素，再加上一个乘幂：（2^k-1）^n
哈哈，这题真简单，要什么容斥原理。。。
代码
1 #include <cstdio>
2 #include <cstring>
3 #include <cstdlib>
4 #include <iostream>
5 using namespace std;
6
7 const int modnum = 1000000007;
8
9 int n, m;
10
11 int pow_mod(long long a, int x)
12 {
13 long long ans = 1;
14 for (long long i = 1; i <= x; i <<= 1)
15 {
16 if (x & i) ans = ans * a % modnum;
17 a = a * a % modnum;
18 }
19 return ans;
20 }
21 void doing()
22 {
23 printf("%dn", pow_mod(pow_mod(2, m) - 1, n));
24 }
25 int main()
26 {
27 while (scanf("%d%d", &n, &m) == 2) doing();
28 return 0;
29 }
- 还没有人评论，欢迎说说您的想法！
客服
