西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)西內(nèi)呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊！！！！
煩死了
煩死了
煩死了
煩死了
題面
一個有 \(n\) 個元素的集合有 \(2^n\) 個不同子集(包含空集), 現(xiàn)在要在這 \(2^n\) 個集合中取出若干集合(至少一個), 使得它們的交集的元素個數(shù)為 \(k\) , 求取法的方案數(shù), 答案模 \(1000000007\) .
(相關(guān)資料圖)
這不就一眼丁真容斥原理么
容斥原理是什么, 不就是一個的減去兩個的加上三個的減去四個的加上五個的... 以此類推一直到邊界么.
類似地, 對于這個題來說, 我們設(shè)交集的元素個數(shù) \(\ge k\) 的方案數(shù)為 \(g_k\) , 答案顯然就是:
\[\sum_{i=k}^{n}(-1)^{i-k} \times g_i\]但是, 這是錯誤的.當(dāng)然也只有這個式子是錯誤的.不是, 并不是錯誤的, 而是不完整的,\(g_i\) 具體是什么我們還不清楚, 所以我們要賦予 \(g_i\) 一個含義.
這里 \(i\) 和 \(k\) 有點混了, 但是它們都是一個東西, 都是 \(g_{某個字母}\) 代表的含義.
為什么呢? 因為雖然是交集元素個數(shù) \(\ge k\) , 但是我們不知道具體是哪 \(k\) 個. 所以 \(g_k\) 中一定有因子 \(\mathrm{C}_n^k\) , 就是在這 \(n\) 個數(shù)中任意選出 \(k\) 個數(shù)來作為交集中一定存在的 \(k\) 個元素.但是這還沒完, 我們還剩下 \(n-k\) 個數(shù), 我們可以讓這 \(n-k\) 個數(shù)構(gòu)成 \(2^{n-k}\) 個集合(包括空集), 把交集中一定存在的 \(k\) 個元素加到這 \(2^{n-k}\) 個集合的每一個里(這 \(2^{n-k}\) 個集合里有一個空集, 加到空集里沒有用, 根據(jù)題意, 顯然不可以兩個相同的集合取交), 變成新的 \(2^{n-k}\) 個集合.那么這 \(2^{n-k}\) 個集合, 無論選多少集合取交集, 交集中一定有之前選出來的 \(k\) 個數(shù). 但是這個交集也有可能有這 \(k\) 個數(shù)以外的數(shù), 所以是交集的元素個數(shù) \(\ge k\) 的方案數(shù). 所以我們把這 \(2^{n-k}\) 個集合看作 \(2^{n-k}\) 個元素, 并讓這 \(2^{n-k}\) 個元素組成新的集合, 顯然可以組成 \(2^{2^{n-k}}\) 個新的集合(顯然新的集合的含義就是每一種取交集的情況). 但是前文已說過不能存在空集 并上 一定存在那 \(k\) 個數(shù)的交集 得到的新的集合, 所以可以組成 \(2^{2^{n-k}}-1\) 個集合.
因為我們剛才論證的結(jié)果是在交集中 \(k\) 個數(shù)確定的情況下論證的, 所以交集的元素個數(shù) \(\ge k\) 的方案數(shù)\(g_k = \mathrm{C}_n^k \times (2^{2^{n-k}} - 1)\) .
然而這個題才剛剛開始
有一個東西叫做二項式反演, 在這里不作主要介紹.這個題用到的二項式反演的基本形式就是:
\[g_k = \sum_{i = k}^{n} \times \mathrm{C}_i^k \times f_i \Leftrightarrow f_k = \sum_{i = k}^{n} \times (-1)^{i - k} \times \mathrm{C}_i^k \times g_i \]其中 \(g_k\) 和上文含義一樣, \(f_k\) 含義為交集元素個數(shù)恰好為 \(k\) 的情況.證明這里就省略了. 思路很無腦, 就是把右面的式子帶入到左面, 再用一個組合數(shù)的性質(zhì) \(\mathrm{C}_n^r \times \mathrm{C}_r^k = \mathrm{C}_n^k \times \mathrm{C}_{n-k}^{r-k}\) 就可以證明. 啊不對, 還得用一次二項式定理.
根據(jù)題意, 我們要求的答案便是 \(f_k\) . 我們將 \(g_i\) 代換, 因為 \(g_i = \mathrm{C}_n^i \times (2^{2^{n-i}} - 1)\) , 所以最后的結(jié)果是:
\[f_k = (\sum_{i = k}^{n} \times (-1)^{i - k} \times \mathrm{C}_i^k \times \mathrm{C}_n^i \times (2^{2^{n-i}} - 1)) \% (1\mathrm{e}9+7)\]利用上面說的組合數(shù)的那個性質(zhì), 也可以寫成:
\[f_k = (\sum_{i = k}^{n} \times (-1)^{i - k} \times \mathrm{C}_n^k \times \mathrm{C}_{n-k}^{i-k} \times (2^{2^{n-i}} - 1)) \% (1\mathrm{e}9+7)\]把 $\mathrm{C}_n^k $ 提出來:
\[f_k = \mathrm{C}_n^k \times (\sum_{i = k}^{n} \times (-1)^{i - k} \times \mathrm{C}_{n-k}^{i-k} \times (2^{2^{n-i}} - 1)) \% (1\mathrm{e}9+7)\]因為在計算的時候要枚舉 \(i\) , 這么寫可以省去其中一項的 \(i\) , 避免冗余計算.
到這里, 式子就推完了.
如何計算
枚舉每一個 \(i\) , 算出每一個 \(i\) 下的結(jié)果, 累加并取模即可.
對于 \((-1)^{i - k}\) , 維護(hù) \(i-k\) 的奇偶性即可.
對于組合數(shù), 因為 \(n \leq 1\mathrm{e}6\) , 所以直接對階乘以及\(\%1\mathrm{e}9 + 7\) 意義下的逆元打表求解即可.
對于 \(2^{2^{n-i}} - 1\) , 需要用到歐拉定理 \(a^{\varphi(p)} \equiv 1 (\mod p), \gcd(a, p) = 1\) .因為我們最后對 \(1\mathrm{e}9 + 7\) 取模(顯然 \(1\mathrm{e}9 + 7\) 是個素數(shù)), 所以 \((2^{2^{n-i}} - 1) \% (1\mathrm{e}9 + 7) = (2^{2^{n-i}} \% (1\mathrm{e}9 + 7) - 1) \% (1\mathrm{e}9 + 7)\) .將歐拉定理變形為 \(a^{\varphi(p)} \% p = 1 \% p = 1, p \neq 1\) , 類似地, 對于 \(2^{2^{n-i}} \% (1\mathrm{e}9 + 7)\) 可變形為 \(2^{2^{n-i} \% \varphi(1\mathrm{e}9 + 7)} \% (1\mathrm{e}9 + 7)\) , 其中 \(\varphi(1\mathrm{e}9 + 7) = 1\mathrm{e}9 + 6\) .對于 \(2^{n-i}\) , 我們可以打表計算 \(2^{某個整數(shù)}\) .
如果不能保證轉(zhuǎn)義都正確, 建議都開 \(long\ long\) .
完結(jié)撒代碼
#include #define LL long longusing namespace std;const LL maxn(1e6 + 5), MOD(1e9 + 7);LL n, k, f[maxn], g[maxn], Pow2[maxn], ans, flag;LL QuickPow(LL a, LL b, LL p) { LL res(1); for (; b; b >>= 1) { if (b & 1) res = res * a % p; a = a * a % p; } return res;}void Init(LL p) { f[0] = g[0] = Pow2[0] = 1; for (int i = 1; i <= n; ++i) { f[i] = f[i - 1] * i % p; g[i] = QuickPow(f[i], p - 2, p) % p; Pow2[i] = (Pow2[i - 1] << 1) % (p - 1); }}LL getC(LL n, LL m, LL p) { if (n < m) return 0; if (n == m || m == 0) return 1; return f[n] * g[m] % p * g[n - m] % p;}int main() { cin >> n >> k; Init(MOD); for (int i = k; i <= n; ++i) { if ((i - k) & 1) ans = ans - getC(n - k, i - k, MOD) % MOD * (QuickPow(2, Pow2[n - i], MOD) - 1) % MOD; else ans = ans + getC(n - k, i - k, MOD) % MOD * (QuickPow(2, Pow2[n - i], MOD) - 1) % MOD; ans = (ans % MOD + MOD) % MOD; } ans = ans * getC(n, k, MOD) % MOD; cout << ans << "\n";} 如有錯誤, 疑問或不同見解, 歡迎評論區(qū)留言.
關(guān)鍵詞：
