bzoj2839 集合计数

F.A.Qs	Home	Discuss	ProblemSet	Status	Ranklist	Contest	入门OJ	ModifyUser	Logout	捐赠本站

2839: 集合计数

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 854 Solved: 470

Description

一个有N个元素的集合有2^N个不同子集（包含空集），现在要在这2^N个集合中取出若干集合（至少一个），使得

它们的交集的元素个数为K，求取法的方案数，答案模1000000007。（是质数喔~）

Input

一行两个整数N,K

Output

一行为答案。

Sample Input

3 2

Sample Output

HINT

【样例说明】

假设原集合为{A,B,C}

则满足条件的方案为：{AB,ABC},{AC,ABC},{BC,ABC},{AB},{AC},{BC}

【数据说明】

对于100%的数据，1≤N≤1000000；0≤K≤N；

Source

HOME Back

答案就是交集至少为k - 至少为k+1......

我们先钦定k个元素，这是C_n^k的。然后发现有2^n-k个集合包含它，这些集合都可以选或不选，所以是2^{2^(n-k)}-1

然后我们发现还是有多算的，至少为j的元素多算了Cjk次，因为我们可以从这Cjk个方案中导出这一种。于是还要乘上这个系数。

那个2的连续阶乘，把上面的对phi(p)取模然后快速幂。

 1 #include <cstdio>
 2 
 3 const int MO = 1000000007, phi = 1000000006;
 4 
 5 const int N = 1000010;
 6 
 7 int f[N], pw[N], pww[N], fac[N], inv[N], invn[N];
 8 
 9 inline int C(int n, int m) {
10     if(n < m || n < 0 || m < 0) return 0;
11     return 1ll * fac[n] * invn[m] % MO * invn[n - m] % MO;
12 }
13 
14 inline int qpow(int a, int b) {
15     int ans = 1;
16     while(b) {
17         if(b & 1) ans = 1ll * ans * a % MO;
18         a = 1ll * a * a % MO;
19         b = b >> 1;
20     }
21     return ans;
22 }
23 
24 int main() {
25 
26     int n, k;
27     scanf("%d%d", &n, &k);
28     pww[0] = pw[0] = fac[0] = inv[0] = invn[0] = 1;
29     fac[1] = inv[1] = invn[1] = 1; pw[1] = pww[1] = 2;
30     for(int i = 2; i <= n; i++) {
31         fac[i] = 1ll * fac[i - 1] * i % MO;
32         inv[i] = 1ll * inv[MO % i] * (MO - MO / i) % MO;
33         invn[i] = 1ll * invn[i - 1] * inv[i] % MO;
34         pw[i] = pw[i - 1] * 2 % MO;
35         pww[i] = pww[i - 1] * 2 % (phi);
36     }
37 
38     int ans = 0;
39     for(int i = k; i <= n; i++) {
40         int temp = 1ll * (qpow(2, pww[n - i]) - 1) * C(n, i) % MO * C(i, k) % MO;
41         if((i - k) & 1) ans = (ans - temp) % MO;
42         else ans = (ans + temp) % MO;
43     }
44     printf("%d
", (ans + MO) % MO);
45     return 0;
46 }

AC代码

还可以用类似bzoj3622的方法，倒着逐步推出正确的结果。虽然会超时但是思想值得借鉴。

 1 #include <cstdio>
 2 
 3 const int MO = 1000000007, phi = 1000000006;
 4 
 5 const int N = 1000010;
 6 
 7 int f[N], pw[N], pww[N], fac[N], inv[N], invn[N];
 8 
 9 inline int C(int n, int m) {
10     if(n < m || n < 0 || m < 0) return 0;
11     return 1ll * fac[n] * invn[m] % MO * invn[n - m] % MO;
12 }
13 
14 inline int qpow(int a, int b) {
15     int ans = 1;
16     while(b) {
17         if(b & 1) ans = 1ll * ans * a % MO;
18         a = 1ll * a * a % MO;
19         b = b >> 1;
20     }
21     return ans;
22 }
23 
24 int main() {
25 
26     
27 
28     int n, k;
29     scanf("%d%d", &n, &k);
30     pww[0] = pw[0] = fac[0] = inv[0] = invn[0] = 1;
31     fac[1] = inv[1] = invn[1] = 1; pw[1] = pww[1] = 2;
32     for(int i = 2; i <= n; i++) {
33         fac[i] = 1ll * fac[i - 1] * i % MO;
34         inv[i] = 1ll * inv[MO % i] * (MO - MO / i) % MO;
35         invn[i] = 1ll * invn[i - 1] * inv[i] % MO;
36         pw[i] = pw[i - 1] * 2 % MO;
37         pww[i] = pww[i - 1] * 2 % (phi);
38     }
39 
40     int ans = 0;
41 
42     /*for(int i = k; i <= n; i++) {
43         int temp = 1ll * (qpow(2, pww[n - i]) - 1) * C(n, i) % MO * C(i, k) % MO;
44         if((i - k) & 1) ans = (ans - temp) % MO;
45         else ans = (ans + temp) % MO;
46     }*/
47     for(int i = n; i >= k; i--) {
48         f[i] = 1ll * (qpow(2, pww[n - i]) - 1) * C(n, i) % MO;
49         for(int j = i + 1; j <= n; j++) {
50             f[i] -= 1ll * f[j] * C(j, i) % MO;
51             if(f[i] < 0) f[i] += MO;
52         }
53     }
54 
55     printf("%d
", (f[k] + MO) % MO);
56     return 0;
57 }

70分TLE代码