COCI2012 TOY

有m种物品，n个箱子之中装着若干物品。问取出一些箱子后，所有m种物品都被选出的方案数。

m<=20,n<=106

这道题很妙啊深刻地利用了容斥

看到n=20，我们就想到了状压和容斥。

怎么容斥呢？我们设A(s)表示状态为s的集合的数量，那么A(2^m-1)就是所求答案。但是这个不好做，那么我们用容斥放缩一下这个条件。我们设B(s)表示状态为s的子集的集合的数量，那么我们可以得到以111为例 B(111)=A(111)+B(110)+B(101)+B(011)-B(100)-B(010)-B(001)+B(000) 那么化简一下 A(111)=B(111)-B(110)-B(101)-B(011)+B(100)+B(010)+B(001)-B(000) 标准的容斥形式。那么剩下的问题就是求出B的值。

我们定义B(s)是s的子集的集合的数量，那么我们只要枚举s的子集就行了，统计数量只要在读入时统计一下就行了。但是枚举子集的复杂度是3^m,过不去，那么我们再优化。

这里我们用了一种分治的方法来优化复杂度，我们利用一种类似cdq分治的办法，把复杂度优化到m*2^m。具体见代码。

然后就是容斥了。

这里证明一下子集枚举的复杂度：我们不妨设二元对(s,t)。那么我们不妨用三进制来表达关系，0s是t的子集，1s和t没关系，2t是s的子集。那么这就是3^m了。

还有一种可以省去popcount的枚举子集的方法，就是用递归，但是程序中没有实现，想知道的可以留个言教导一下蒟蒻。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = , mod = ;

int n, all, m;

ll ans;

int c[N], d[N];

inline ll power(ll x, ll t)

{

    ll ret = ;

    for(; t; t >>= , x = x * x % mod) if(t & ) ret = ret * x % mod;

    return ret;

}

void build(int l, int r)

{

    if(l > r) return;

    if(l == r) { c[l] = d[l]; return; }

    int mid = (l + r) >> ;

    build(l, mid); build(mid + , r);

    for(int i = l; i <= mid; ++i) c[i + mid - l + ] = (c[i + mid - l + ] + c[i]) % mod;

}

int main()

{

    scanf("%d%d", &n, &m); all =  << m;

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

    {

        int num, tot = ; scanf("%d", &num);

        while(num--)

        {

            int x; scanf("%d", &x); --x;

            tot |= ( << x);

        }

        ++d[tot];

    }

    build(, all - );

    for(int i = ; i < all; ++i)

    {

        int x = __builtin_popcount(i);

        if((x % ) == (m % )) ans = (ans + power(, c[i])) % mod; else ans = ((ans - power(, c[i])) % mod + mod) % mod;

    }

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

    return ;

}

巴特西

COCI2012 TOY

最新文章

热门文章