ZR#999

解法：

一道计数题，看到要求必须 $ m $ 个标号，所有标号至少出现一次的方案。

很容易想到可以容斥，但容斥这个东西是一种很神奇的东西，你可以看出来一道题需要容斥，但你就是不知道怎么容斥。

原题的等价形式为：总方案减去至少不出现一种玩具的方案数。

考虑容斥，那么就有

$ \bigcup ^ {n} _ {i = 1} A_i = \sum ^ {n} _ {k = 1} (-1) ^ {k-1} \sum _ {1 \leq i_1 < i_2 \cdots i_k \leq n} \mid A_{i_1} \cap A_{i_2} \cap \cdots \cap A _ {i_k} \mid $

设 $ f_i $ 表示状态为 $ i $ 时所有元素都在集合 $ i $ 中的方案数。（不要求包含 $ i $ 中的所有元素）然后用容斥原理算一下即可。

但是这个题数据范围比较大，需要用 $ FWT $ （高维前缀和）来维护。

CODE:

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define N 1 << 20

const int p = 1e9 + 7;

int n,m,k,x,res,ans;

int f[N],t[N],cnt[N],flag;

inline int read() {

    int x = 0, f = 1;

    char ch = getchar();

    while(ch < '0' || ch > '9') {if (ch == '-')f = -1; ch = getchar();}

    while(ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}

    return x * f;

}

int main() {

    n = read(),m = read();

    flag = (1 << m) - 1;

    cnt[0] = 1;

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

        k = read();

        res = 0;

        for(int j = 1 ; j <= k ; j++) {

            x = read();

            res |= 1 << (x - 1);

        }

        ++f[res];

    }

    for(int i = 1 ; i <= m ; i++) {

        for(int j = 1 ; j <= flag  ; j++) {

            if(j & (1 << (i - 1)))

                f[j] += f[j ^ (1 << (i - 1))];

        }

    }

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

        cnt[i] = cnt[i - 1] << 1;

        if(cnt[i] >= p) cnt[i] -= p;

    }

    for(int i = 0 ; i <= flag ; i++) {

        t[i] =  t[i >> 1] + i & 1;

        if(!((m - t[i]) & 1)) ans += cnt[f[i]] - 1;

        else ans -= cnt[f[i]] - 1;

        if(ans >= p) ans %= p;

        else if(ans < 0) ans += p;

    }

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

    //system("pause");

    return 0;

}

巴特西

ZR#999

ZR#999

解法：

CODE:

最新文章

热门文章