Description

題庫鏈接

有 \(2^n\) 個集合，每個集合只包含 \([1,n]\) ，且這些集合兩兩不同。問有多少種選擇方法（至少選一個），使得這些集合交集大小為 \(k\) 。

\(0\leq k\leq n\leq 1000000\)

Solution

設 \(f(n)\) 為交集元素大于 \(k\) 的方案數，設 \(g(n)\) 為交集元素等于 \(k\) 的方案數。

容易得到

\[f(k)=\sum_{i=k}^n{i\choose k}g(i)\Rightarrow g(k)=\sum_{i=k}^n(-1)^{i-k}{i\choose k}f(i)\]

并且 \(f(i)={n\choose i}2^{2^{n-i}}\) 。

直接求就好了。

Code

#include <bits/stdc++.h> using namespace std; const int N = 1000000+5, yzh = 1000000007;int n, k, ifac[N], fac[N], ans;int quick_pow(int a, int b, int p) {int ans = 1;while (b) {if (b&1) ans = 1ll*ans*a%p;b >>= 1, a = 1ll*a*a%p;}return ans; } int C(int n, int m) {return 1ll*fac[n]*ifac[m]%yzh*ifac[n-m]%yzh; } void work() {scanf("%d%d", &n, &k);fac[0] = fac[1] = ifac[0] = ifac[1] = 1;for (int i = 2; i <= n; i++) ifac[i] = -1ll*yzh/i*ifac[yzh%i]%yzh;for (int i = 2; i <= n; i++)fac[i] = 1ll*fac[i-1]*i%yzh, ifac[i] = 1ll*ifac[i]*ifac[i-1]%yzh;for (int i = k; i <= n; i++)if ((i-k)&1) (ans -= 1ll*C(i, k)*C(n, i)%yzh*quick_pow(2, quick_pow(2, n-i, yzh-1), yzh)%yzh) %= yzh;else (ans += 1ll*C(i, k)*C(n, i)%yzh*quick_pow(2, quick_pow(2, n-i, yzh-1), yzh)%yzh) %= yzh;printf("%d\n", (ans+yzh)%yzh); } int main() {work(); return 0; }

轉載于:https://www.cnblogs.com/NaVi-Awson/p/9245549.html

總結

以上是生活随笔為你收集整理的[BZOJ 2839]集合计数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。