题解 P3220 【[HNOI2012]与非】

Salamander · 2018-02-02 10:54:44 · 题解

与非(nand)是非常强大的位运算，可以表示出其他所有的位运算：

not\ A=A\ nand\ A

A\ and\ B=not\ (A\ nand\ B)

A\ or\ B=(not\ A)\ nand\ (not\ B)

A\ xor\ B=(A\ and\ not\ B)\ or\ (not\ A\ and\ B)

所以相当于是这n个数之间可以做任何位运算。

然后我们考虑一下位与位之间的限制。如果这n个数中每个数的第i位和第j位都相同，那么这n个数无论怎么运算，最后得到的答案中第i位和第j位一定相同。我们在数位dp的时候从高位到低位考虑，确定了当前位后把必须和它相同的位也标记一下，就可以求出[1,n]中能运算出的数的个数。

为什么这样是对的?其他没有互相限制的位置上就一定可以任意取0或1了吗?

类似于线性基的思想，我们可以构造这样一种方案：通过一些运算把某一位上只留下一个1，其他的数在这一位上都为0，最后用它们或起来就可以构造出任意一个数。对于第i位，假设没有限制，那么我们把这一位上为0的数全都取反，然后全部与起来，得到的数这一位上肯定是1；同时由于这一位没有限制，所以不会有其他位置上再出现一个1，因为如果还出现1就表每一个数中那一位与第i位都相等，于是就产生了限制，矛盾。所以对于没有限制的位，我们一定可以构造出一个只有这一位上为1的数。对于几个必须相等的位，这样可以构造出一个只有这几位为1的数。

于是我们可以把n个数构造出一个类似这样的东西，假设最左边第1位，那么下面这个东西中间的限制就是第3位和第5位必须相等，第8位和第9位必须相等。

利用这样的东西，我们通过他们之间的或运算，就可以构造出原来n个数所能构造出的所有数，所以数位dp就可以直接做了。首先暴力求出哪些位必须相等。

复杂度应该是O(nk^2)。

#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define For(i,_beg,_end) for(int i=(_beg),i##end=(_end);i<=i##end;++i)
#define Rep(i,_beg,_end) for(int i=(_beg),i##end=(_end);i>=i##end;--i)

template<typename T>T Max(const T &x,const T &y){return x<y?y:x;}
template<typename T>T Min(const T &x,const T &y){return x<y?x:y;}
template<typename T>int chkmax(T &x,const T &y){return x<y?(x=y,1):0;}
template<typename T>int chkmin(T &x,const T &y){return x>y?(x=y,1):0;}
template<typename T>void read(T &x){
    T f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(x=0;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
    x*=f;
}

typedef long long LL;
const int maxn=1010;
int n,k,c[65],tmp[65];
LL a[maxn],L,R;
vector<int>pos[65];

LL Dfs(LL n,int x,bool lim){
    if(x<0)return 1;
    if(!lim){
        int cnt=0;
        memcpy(tmp,c,sizeof c);
        Rep(i,x,0) if(tmp[i]==-1){
            cnt++;
            For(j,0,pos[i].size()-1) tmp[pos[i][j]]=1;
        }
        return 1LL<<cnt;
    }
    LL res=0;
    if(c[x]==-1){
        For(i,0,(n>>x)&1){
            For(j,0,pos[x].size()-1) c[pos[x][j]]=i;
            res+=Dfs(n,x-1,lim&(i==((n>>x)&1)));
        }
        For(j,0,pos[x].size()-1) c[pos[x][j]]=-1;
        return res;
    }
    else{
        if(c[x]&&lim&&!((n>>x)&1))return 0;
        return Dfs(n,x-1,lim&(c[x]==((n>>x)&1)));
    }
}
LL Solve(LL x){
    memset(c,-1,sizeof c);
    if(x<0)return 0;
    return Dfs(x,k-1,(x>>k)?0:1);
}

int main(){
    read(n);read(k);read(L);read(R);
    For(i,1,n) read(a[i]);
    Rep(i,k-1,1) Rep(j,i-1,0){
        bool flag=true;
        For(p,1,n) if(((a[p]>>i)&1)^((a[p]>>j)&1)){
            flag=false;
            break;
        }
        if(flag) pos[i].push_back(j);
    }
    printf("%lld\n",Solve(R)-Solve(L-1));
    return 0;
}