Description

題庫鏈接

在集合 \(S=\{1,2,...,n\}\) 中選出 \(m\) 個子集，滿足三點性質：

所有選出的 \(m\) 個子集都不能為空。

所有選出的 \(m\) 個子集中，不能存在兩個完全一樣的集合。

所有選出的 \(m\) 個子集中， \(1\) 到 \(n\) 每個元素出現的次數必須是偶數。

\(1\leq n,m\leq 1000000\)

Solution

一開始想著去容斥出現奇數次的元素。發現是 \(O(n^2)\) 的。只好去頹題解了...

轉化一下思路，注意到這樣一個性質：假若我要選出 \(i\) 個子集，只要我選出了 \(i-1\) 個子集，那么剩下一個子集是存在且唯一的。

注意到這樣的性質，容易發現剩下的 \(DP\) 過程就和 [BZOJ 2169]連邊 的思路是類似的。

類似地，記 \(f_i\) 為有序地選出 \(i\) 個非空集合的合法方案數。由上面所說的 \(f_i=A_{2^n-1}^i\) 。但是這樣會有不合法的情況。

首先，我們試著考慮去掉不滿足 \(1\) 的條件。顯然為空的集合只會是最后一個被動選的集合，那么不滿足該情況的方案有 \(f_{i-1}\) 種；

其次再看不滿足 \(2\) 情況的方案數。顯然重復只會和 \(i-1\) 個集合中的 \(1\) 個集合重復。這樣的條件為 \(f_{i-2}\cdot(2^n-1-(i-2))\cdot(i-1)\) 。

有序變無序答案就是 \(\frac{f_m}{m!}\) 。

Code

//It is made by Awson on 2018.3.4 #include <bits/stdc++.h> #define LL long long #define dob complex<double> #define Abs(a) ((a) < 0 ? (-(a)) : (a)) #define Max(a, b) ((a) > (b) ? (a) : (b)) #define Min(a, b) ((a) < (b) ? (a) : (b)) #define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b)) #define writeln(x) (write(x), putchar('\n')) #define lowbit(x) ((x)&(-(x))) using namespace std; const int yzh = 100000007, N = 1000000; void read(int &x) {char ch; bool flag = 0;for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());x *= 1-2*flag; } void print(int x) {if (x > 9) print(x/10); putchar(x%10+48); } void write(int x) {if (x < 0) putchar('-'); print(Abs(x)); }int n, m, A[N+5], f[N+5];int quick_pow(int a, int b) {int ans = 1;while (b) {if (b&1) ans = 1ll*ans*a%yzh;a = 1ll*a*a%yzh, b >>= 1;}return ans; } void work() {read(n), read(m); n = quick_pow(2, n)-1; f[0] = 1;A[1] = n; for (int i = 2; i <= m; i++) A[i] = 1ll*A[i-1]*(n-i+1)%yzh;for (int i = 2; i <= m; i++) f[i] = (A[i-1]-f[i-1])%yzh, f[i] = (f[i]-1ll*f[i-2]*(n-i+2)%yzh*(i-1)%yzh)%yzh;int t = 1; for (int i = 1; i <= m; i++) t = 1ll*i*t%yzh; t = 1ll*f[m]*quick_pow(t, yzh-2)%yzh;writeln((t+yzh)%yzh); } int main() {work(); return 0; }

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

總結

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

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