[HNOI 2011]卡农

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;

}

巴特西

[HNOI 2011]卡农

Description

Solution

Code

最新文章

热门文章