BJ模拟:and(容斥)
程序员文章站
2023-12-25 08:34:21
...
题解:
我反过来用类似记忆化搜索的方式实现的,具体看代码。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int,int> pii;
const int RLEN=1<<18|1;
inline char nc() {
static char ibuf[RLEN],*ib,*ob;
(ib==ob) && (ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
return (ib==ob) ? -1 : *ib++;
}
inline int rd() {
char ch=nc(); int i=0,f=1;
while(!isdigit(ch)) {if(ch=='-')f=-1; ch=nc();}
while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0'; ch=nc();}
return i*f;
}
inline void W(LL x) {
static int buf[50];
if(!x) {putchar('0'); return;}
if(x<0) {putchar('-'); x=-x;}
while(x) {buf[++buf[0]]=x%10; x/=10;}
while(buf[0]) putchar(buf[buf[0]--]+'0');
}
const int N=1<<13, mod=1e9+7;
inline int add(int x,int y) {return (x+y>=mod) ? (x+y-mod) : (x+y);}
inline int dec(int x,int y) {return (x-y<0) ? (x-y+mod) : (x-y);}
int n, a[N]; LL f[2][N+50][N+50];
int main() {
n=rd();
for(int i=1; i<=n; i++) a[i]=rd();
int now=1, lim=(1<<13)-1;
for(int i=1; i<=n; i++) a[i]^=lim;
f[now][lim][0]++;
for(int p=n;p>=1;p--) {
now^=1;
for(int i=0;i<=lim;i++)
for(int j=i;;j=(j-1)&i) {
f[now][i][j]=f[now^1][i|a[p]][j-(j&a[p])];
f[now][i][j]-=f[now^1][i|a[p]][(j-(j&a[p]))|(a[p]-(a[p]&i))];
f[now][i][j]+=f[now^1][i][j];
if(!j) break;
}
}
printf("%d\n",f[now][0][0]%mod);
}