CF 449D 题解（状压+容斥）

状压妙啊...

本题的主体思路：状压+容斥原理（或状压+数位dp）

记g[i]表示按位与后结果所有位上至少有i个1的方案数

那么根据容斥原理，ans=g[0]-g[1]+g[2]-g[3]+g[4]...

于是如果我们求出了g，就可以求出ans

可是怎么求出g呢

我们记f[i]表示a&i==i这样的a的个数，那么如果i某一位上为1，则a这一位上也为1

于是我们可以枚举所有可能的结果（0-10^6），然后观察这个结果是否是某一个可能结果的子集，如果是的话就累计个数

详细说一下，就是我首先读入所有数据，每读入一个数据x记录f[x]++作为初始值，然后不断更新

在更新的时候，我们首先枚举每一位j，然后枚举1~10^6的所有值i，如果某个值这一位上是1，则更新：

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

就是去掉j位的个数加上i

什么?怎么证明这样统计是不重不漏的？

首先，我们是按位枚举的，一开始只有初始读入的部分有值，剩下的没有值。那么，当我们枚举第一位时，我们只会更新由初值去掉第一位所能获得的所有值

以此类推，当我们更新第二位时，我们只会更新初值去掉前两位和初值只去掉第二位能获得的所有值

也就是说，我们在更新每一位时，都不会产生重复的状态，都是原来的状态+这一位，所以是不重的，而由于这样的枚举能够遍历所有数位的组合，所以也是不漏的

好，我们处理出了f，接下来？

我们可以枚举所有结果，统计他有几位上是1，那么如果有1位上是1，就会对g[1]产生贡献，等等，以此类推

然后我们再考虑，产生多少贡献？

我们会发现，如果这个结果对应的数有k个，那么答案应为2^k-1（即每个数都有选或不选两种状态，但不能全不选）

所以他产生的贡献就是2^k-1

什么？这种方法的正确性何在？

首先，根据容斥原理，答案的正确性是很显然的

那么我们只需证明g求解的正确性即可

首先回顾一下g的定义：“至少”包含i个1的取法的方案数

也就是说，我所找出的东西数位中1的个数只需>=i即可

那这个是很显然能够保证的

于是为什么不重呢？

由于每个结果互不相同，而我们最后事实上是按结果取的，所以每一种取法都是互不相同的，保证了正确性。

最后代码：

#include <cstdio>

#include <iostream>

#define ll long long

#define mode 1000000007

#define maxx 1000000

ll v[];

ll dp[];

ll f[];

int n;

int main()

{

    v[]=;

    scanf("%d",&n);

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

    {

        v[i]=(v[i-]<<)%mode;

    }

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

    {

        int x;

        scanf("%d",&x);

        dp[x]++;

    }

    for(int j=;j<=;j++)

    {

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

        {

            if(((<<j)&i))

            {

                dp[i^(<<j)]+=dp[i];

            }

        }

    }

    ll ans=;

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

    {

        int cnt=;

        for(int j=;j<=;j++)

        {

            if((<<j)&i)

            {

                cnt++;

            }

        }

        f[cnt]+=((v[dp[i]]-)%mode+mode)%mode;

    }

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

    {

        if(i%)

        {

            ans-=f[i];

            ans%=mode;

        }else

        {

            ans+=f[i];

            ans%=mode;

        }

    }

    printf("%I64d\n",(ans%mode+mode)%mode);

    return ;

}

巴特西

CF 449D 题解（状压+容斥）

最新文章

热门文章