CF449D Jzzhu and Numbers (状压DP+容斥)

题目大意：

给出一个长度为n的序列，构造出一个序列使得它们的位与和为0，求方案数

也就是从序列里面选出一个非空子集使这些数按位与起来为0.

看了好久才明白题解在干嘛，我们先要表示出两两组合位与和为0的所有情况

先hx一下每个数出现的次数，然后我们从遍历 i ，i 是二进制的数位

然后遍历所有的情况，如果第 i 位有1，那么说明我们去掉第 i 位的1就是又一种情况！

其实我们统计的是所有数在删掉/不删掉每一位的1 所有可能出现的数！

那么，状态内任意组合，不能取空集，把空集加上的话，会发现其实是二项式定理的展开，总数就是 $2^k -1$

仍然不是很理解，明天再思考思考

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #define ll long long

 #define N (1<<20)+100

 #define maxn 1000000

 #define mod 1000000007

 using namespace std;

 int n;

 int hx[N];

 ll xx,yy,tt;

 ll pw[N],sum[N],ans[];

 void get_pw() {pw[]=;for(ll i=;i<=n+;i++) pw[i]=(pw[i-]*(ll))%mod;}

 int main()

 {

     freopen("data.in","r",stdin);

     scanf("%d",&n);

     int x;

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

     {

         scanf("%d",&x);

         hx[x]++;

         sum[x]=hx[x];

     }

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

     {

         for(int s=(<<)-;s>=;s--)

             if(s&(<<j)) sum[s^(<<j)]+=sum[s];

     }

     get_pw();

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

     {

         int cnt=;

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

             if(s&(<<j))

                 cnt++;

         ans[cnt]+=((pw[sum[s]]-)%mod+mod)%mod;

         ans[cnt]%=mod;

     }

     ll ret=;

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

     {

         if(i&) ret-=ans[i],ret%=mod;

         else    ret+=ans[i],ret%=mod;

     }

     printf("%lld\n",(ret%mod+mod)%mod);

     return ;

 }

巴特西

CF449D Jzzhu and Numbers (状压DP+容斥)

最新文章

热门文章