[HNOI2012]与非

发表于 | 分类于

题目描述

NAND（与非）是一种二元逻辑运算，其运算结果为真当且仅当两个输入的布尔值不全为真。NAND运算的真值表如下（1表示真，0表示假）:

A B A NAND B
0 0 1
0 1 1
1 0 1
1 1 0

两个非负整数的NAND是指将它们表示成二进制数，再在对应的二进制位进行NAND运算。由于两个二进制数的长度可能不等，因此一般约定一个最高位K，使得两个数的二进制表示都不 超过K位，不足K位的在高位补零。给定N个非负整数A1,A2……AN和约定位数K，利用NAND运算与括号，每个数可以使用任意次，请你求出范围[L,R]内可以被计算出的数有多少个。

输入输出格式

输入格式：
输入文件第一行是用空格隔开的四个正整数N，K，L和R，接下来的一行是N个非负整数A1,A2……AN，其含义如上所述。 100%的数据满足K<=60且N<=1000,0<=Ai<=2^k-1,0<=L<=R<=10^18

输出格式：
仅包含一个整数，表示[L,R]内可以被计算出的数的个数

输入输出样例

输入样例：
3 3 1 4
3 4 5
输出样例：
4

说明

样例1中，(3 NAND 4) NADN (3 NAND 5) = 1，5 NAND 5 = 2，3和4直接可得。

分析

被long long的<<卡死。。。

A NAND B 相当于 !(A&B)
而!(A&A)=!A，因此有了!的操作
!(A NAND B)=A&B，因此有了&的操作
如有第i位对于其他任意一位在n个数中至少有a[x][i]!=a[x][j]
则可形成形如000001000的数
否则尽量可得到类似形如001001001的数
从而得出结论只要满足这些位相同的要求，可生成任意数
利用并查集数位dp
参考题解

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
int n,K,cnt;
ll L,R;
int bit[1010][66],fa[66];
int a[66];
bool mp[66][66];
int find(int x)
{
    if (fa[x]==x) return x;
    fa[x]=find(fa[x]);
    return fa[x];
}
ll sol(ll x)
{
    ++x;
    if (x>=(1ll<<K)) return 1ll<<cnt;
    int br[66],num=cnt;
    ll ans=0;
    memset(br,-1,sizeof(br));
    for (int i=K;i>=1;--i)
    {
        if ((x>>(i-1))&1)
        {
            if (br[find(i)]==1) continue;
            if (br[find(i)]==-1) --num,br[find(i)]=1;
            ans+=(1ll<<num);
            if (br[find(i)]==0) break;
        }
        else
        {
            if (br[find(i)]==-1) --num,br[find(i)]=0;
            if (br[find(i)]==1) break;
        }
    }
    return ans;
    
}
int main()
{
    scanf("%d%d%lld%lld",&n,&K,&L,&R);
    ll x;
    for (int i=1;i<=n;++i)
    {
        scanf("%lld",&x);
        int cc=0;
        while (x)
        {
            ++cc;
            if (x%2) bit[i][cc]=1;
            x/=2;
        }
    }
    for (int j=1;j<=K;++j)
        for (int k=1;k<=K;++k)
        if (j!=k)
            if (bit[1][j]==bit[1][k]) mp[j][k]=1;
    for (int i=2;i<=n;++i)
        for (int j=1;j<=K;++j)
        for (int k=1;k<=K;++k)
            if (bit[i][j]!=bit[i][k]) mp[j][k]=0;
    
    for (int i=1;i<=K;++i)
        fa[i]=i;
    for (int j=1;j<=K;++j)
        for (int k=1;k<=K;++k)
            if (mp[j][k])
            {
                int c=find(k); 
                int d=find(j);
                if (c!=d) fa[c]=d;
            }
    for (int i=1;i<=K;++i)
        if (fa[i]==i) ++cnt;
    printf("%lld\n",sol(R)-sol(L-1));
    return 0;
}
--------------------------