首页 > 代码库 > Codeforces 449D：Jzzhu and Numbers（高维前缀和）
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（高维前缀和）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。