BJ模拟 and【容斥】
程序员文章站
2023-12-24 22:08:39
...
题目描述:
解题思路:
#include<bits/stdc++.h>
using namespace std;
int getint()
{
int i=0,f=1;char c;
for(c=getchar();c!='-'&&(c<'0'||c>'9');c=getchar());
if(c=='-')f=-1,c=getchar();
for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';
return i*f;
}
const int N=51,mx=(1<<13)-1,mod=1e9+7;
int n,a[N],f[2][1<<13][1<<13];
inline void add(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
inline void dec(int &x,int y){x=x-y>=0?x-y:x-y+mod;}
int main()
{
//freopen("lx.in","r",stdin);
//freopen("lx.out","w",stdout);
n=getint();
for(int i=1;i<=n;i++)a[i]=getint()^mx;
int now=0;f[now][0][0]=1;
for(int i=0;i<n;i++,now^=1)
for(int s1=0;s1<=mx;s1++)
for(int s2=s1;;s2=(s2-1)&s1)
{
if(!f[now][s1][s2])
{
if(!s2)break;
continue;
}
add(f[now^1][s1][s2],f[now][s1][s2]);
add(f[now^1][s1|a[i+1]][s2^(s2&a[i+1])],f[now][s1][s2]);
dec(f[now^1][s1|a[i+1]][(s2^(s2&a[i+1]))|(a[i+1]^(a[i+1]&s1))],f[now][s1][s2]);
f[now][s1][s2]=0;
if(!s2)break;
}
cout<<f[now][mx][0]<<'\n';
return 0;
}
推荐阅读
-
BJ模拟 and【容斥】
-
Codeforces Round #258 (Div. 2)Devu and Flowers 容斥原理_html/css_WEB-ITnose
-
BZOJ2339: [HNOI2011]卡农(dp 容斥)
-
cf449D. Jzzhu and Numbers(容斥原理 高维前缀和)
-
容斥问题
-
cf997C. Sky Full of Stars(组合数 容斥)
-
BZOJ2005: [Noi2010]能量采集(容斥原理 莫比乌斯反演)
-
AtCoder Beginner Contest 173(E 思维模拟 F 容斥 思维题 )
-
cf1043F. Make It One(dp 容斥原理)
-
BZOJ2440: [中山市选2011]完全平方数(莫比乌斯+容斥原理)