bzoj2839 集合计数

2023-02-23 09:13:13

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)取模然后快速幂。

 #include <cstdio>

 const int MO = , phi = ;

 const int N = ;

 int f[N], pw[N], pww[N], fac[N], inv[N], invn[N];

 inline int C(int n, int m) {

     if(n < m || n <  || m < ) return ;

     return 1ll * fac[n] * invn[m] % MO * invn[n - m] % MO;

 }

 inline int qpow(int a, int b) {

     int ans = ;

     while(b) {

         if(b & ) ans = 1ll * ans * a % MO;

         a = 1ll * a * a % MO;

         b = b >> ;

     }

     return ans;

 }

 int main() {

     int n, k;

     scanf("%d%d", &n, &k);

     pww[] = pw[] = fac[] = inv[] = invn[] = ;

     fac[] = inv[] = invn[] = ; pw[] = pww[] = ;

     for(int i = ; i <= n; i++) {

         fac[i] = 1ll * fac[i - ] * i % MO;

         inv[i] = 1ll * inv[MO % i] * (MO - MO / i) % MO;

         invn[i] = 1ll * invn[i - ] * inv[i] % MO;

         pw[i] = pw[i - ] *  % MO;

         pww[i] = pww[i - ] *  % (phi);

     }

     int ans = ;

     for(int i = k; i <= n; i++) {

         int temp = 1ll * (qpow(, pww[n - i]) - ) * C(n, i) % MO * C(i, k) % MO;

         if((i - k) & ) ans = (ans - temp) % MO;

         else ans = (ans + temp) % MO;

     }

     printf("%d\n", (ans + MO) % MO);

     return ;

 }

AC代码

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

 #include <cstdio>

 const int MO = , phi = ;

 const int N = ;

 int f[N], pw[N], pww[N], fac[N], inv[N], invn[N];

 inline int C(int n, int m) {

     if(n < m || n <  || m < ) return ;

     return 1ll * fac[n] * invn[m] % MO * invn[n - m] % MO;

 }

 inline int qpow(int a, int b) {

     int ans = ;

     while(b) {

         if(b & ) ans = 1ll * ans * a % MO;

         a = 1ll * a * a % MO;

         b = b >> ;

     }

     return ans;

 }

 int main() {

     int n, k;

     scanf("%d%d", &n, &k);

     pww[] = pw[] = fac[] = inv[] = invn[] = ;

     fac[] = inv[] = invn[] = ; pw[] = pww[] = ;

     for(int i = ; i <= n; i++) {

         fac[i] = 1ll * fac[i - ] * i % MO;

         inv[i] = 1ll * inv[MO % i] * (MO - MO / i) % MO;

         invn[i] = 1ll * invn[i - ] * inv[i] % MO;

         pw[i] = pw[i - ] *  % MO;

         pww[i] = pww[i - ] *  % (phi);

     }

     int ans = ;

     /*for(int i = k; i <= n; i++) {

         int temp = 1ll * (qpow(2, pww[n - i]) - 1) * C(n, i) % MO * C(i, k) % MO;

         if((i - k) & 1) ans = (ans - temp) % MO;

         else ans = (ans + temp) % MO;

     }*/

     for(int i = n; i >= k; i--) {

         f[i] = 1ll * (qpow(, pww[n - i]) - ) * C(n, i) % MO;

         for(int j = i + ; j <= n; j++) {

             f[i] -= 1ll * f[j] * C(j, i) % MO;

             if(f[i] < ) f[i] += MO;

         }

     }

     printf("%d\n", (f[k] + MO) % MO);

     return ;

 }

70分TLE代码

码农公寓