欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

BJ模拟:and(容斥)

程序员文章站 2023-12-25 08:34:21
...

传送门

题解:
BJ模拟:and(容斥)

我反过来用类似记忆化搜索的方式实现的,具体看代码。

#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);
}

上一篇:

下一篇: