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

BJ模拟 and【容斥】

程序员文章站 2023-12-24 22:08:39
...

题目描述:

BJ模拟 and【容斥】

解题思路:

BJ模拟 and【容斥】

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

上一篇:

下一篇: