Codeforces 449D Jzzhu and Numbers（高维前缀和）

【题目链接】 http://codeforces.com/problemset/problem/449/D

【题目大意】

　　给出一些数字，问其选出一些数字作or为0的方案数有多少

【题解】

　　题目等价于给出一些集合，问其交集为空集的方案数，
　　我们先求交集为S的方案数，记为dp[S]，发现处理起来还是比较麻烦，
　　我们放缩一下条件，求出交集包含S的方案数，记为dp[S]，
　　我们发现dp[S]，是以其为子集的方案的高维前缀和，
　　我们逆序求高维前缀和即可，之后考虑容斥，求出交集为0的情况，
　　我们发现这个容斥实质上等价于高维的前缀差分，
　　那么我们利用之前的代码，修改一下参数就能得到答案。

【代码】

#include <cstdio>

#include <algorithm>

using namespace std;

const int mod=1000000007;

typedef long long LL;

int all,n,m,x;

struct data{

    int val;

    data operator +(const data &rhs)const{

        int t_val=val+rhs.val;

        if(t_val>=mod)t_val-=mod;

        if(t_val<0)t_val+=mod;

        return data{t_val};

    }

    data operator *(const int &rhs)const{

	    int t_val=val*rhs;

	    return data{t_val};

	}

}dp[(1<<20)+10];

LL pow(LL a,LL b,LL p){LL t=1;for(a%=p;b;b>>=1LL,a=a*a%p)if(b&1LL)t=t*a%p;return t;}

void doit(data dp[],int n,int f){

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

        for(int j=all-1;j>=0;j--){

             if(~j&(1<<i))dp[j]=dp[j]+dp[j|(1<<i)]*f;

        }

    }

}

int main(){

    scanf("%d",&n);

    all=(1<<20);

    for(int i=0;i<n;i++){scanf("%d",&x);dp[x].val++;}

    doit(dp,20,1);

    for(int i=0;i<all;i++)dp[i].val=pow(2,dp[i].val,mod);

    doit(dp,20,-1);

    printf("%d\n",dp[0].val);

    return 0;

}

巴特西

Codeforces 449D Jzzhu and Numbers（高维前缀和）

最新文章

热门文章