P3220 [HNOI2012]与非[数位dp]

题目描述

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

img

()

两个非负整数的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]内可以被计算出的数的个数

输入输出样例

输入样例#1:

1
2
3  3 1 4
3 4 5

输出样例#1:

1
4

说明

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

题解

doe教我的。

时间复杂度 $O(nk^2)$,数位dp部分是 $O(k)$的

a NAND b,相当于!(a&b)

1.比较显然的一点,如果$n$个数,每个数的第$i$位和第$j$位都相同,那么最后的结果这两位一定相同。

2.a NAND a相当于 !a,然后其他的都可以构造出来(对于某两位01,01 NAND 01=10,10 NAND 01=11,11 NAND 11 = 00,这样就都可以构造出来了)

对于1,我们可以把这些位用并查集连起来,然后数位dp的时候判一下就好了。当不受限制的时候,直接返回 2的总块数-已经取了的块数(集合数)的次方。

注意:$l$可能会等于 $0$, $l$ 和 $r$ 会大于 $2^k-1$

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int qmax(int &x,int y) {if (x<y) x=y;}
int qmin(int &x,int y) {if (x>y) x=y;}
ll read()
{
char s;ll k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s)));
if(s=='-')base=-1,s=getchar();
while(isdigit(s)){k=k*10+(s^'0');s=getchar();}
return k*base;
}
void write(int x)
{
if(x<0){putchar('-');write(-x);}
else{if(x/10)write(x/10);putchar(x%10+'0');}
}
int n,k,kuai;
ll l,r,a[1010];
int A[70],now[70];
int fa[70],bj[70];
long long b[1010][70];
int gf(int x) {return fa[x]==x?x:fa[x]=gf(fa[x]);}
void chai(int x)
{
ll X=a[x];int i=0;
if (X==0) return;
while (X>0) b[x][++i]=X&1LL,X>>=1LL;
}//把每一个数拆了
ll dfs(int pos,int flag,int cnt)
{
if (pos==0) return 1;
if (A[pos]==0&&flag)//这一位最大为0
{
if (fa[pos]!=pos&&(bj[pos]^now[gf(pos)])==1) return 0;//被限制为1了
if (fa[pos]!=pos&&(bj[pos]^now[gf(pos)])==0) return dfs(pos-1,flag,cnt);
now[pos]=0;
return dfs(pos-1,flag,cnt+1);
}
if (A[pos]==1&&flag)
{
if (fa[pos]!=pos&&(bj[pos]^now[gf(pos)])==1) return dfs(pos-1,flag,cnt);//被限制为1往后扫
if (fa[pos]!=pos&&(bj[pos]^now[gf(pos)])==0) return 1LL<<(kuai-cnt);//不受限制直接返回
now[pos]=1;//等于1的情况
ll s1=dfs(pos-1,flag,cnt+1);
now[pos]=0;//等于0的情况(其实可以直接返回,但是偷懒
s1+=dfs(pos-1,0,cnt+1);
return s1;
}
if (!flag) return 1LL<<(kuai-cnt);//直接返回
}
ll qans(ll x)
{
if (x<0) return 0;
int p=0;ll l1=x;ll ss=0;
memset(A,0,sizeof(A));
memset(now,0,sizeof(now));
while (l1) A[++p]=l1%2,l1>>=1LL;
if (p>k)//特判
{
return dfs(k,0,0);
}
if (A[k]==1)
{//第一位的限制为1可以直接返回
now[k]=1;
ss+=dfs(k-1,1,1);
now[k]=0;
ss+=dfs(k-1,0,1);
} else
{
now[k]=0;
ss+=dfs(k-1,1,1);
}
return ss;
}
ll ans;
int main()
{
n=read();k=read();l=read();r=read();

for (int i=1;i<=n;i++) {a[i]=read();chai(i);}
for (int i=1;i<=k;i++) fa[i]=i;
for (int i=1;i<=k;i++)
for (int j=i+1;j<=k;j++)
{//预处理,然后合并
int flag1=1,X,Y;
if (b[1][i]!=b[1][j]) continue;
for (int l=2;l<=n;l++)
if (b[l][i]!=b[l][j]) {flag1=0;break;}
if (flag1)
{
X=gf(i),Y=gf(j);
if (X<Y) swap(X,Y);
fa[Y]=X;
}
}
for (int i=k;i>=1;i--)
{
if (gf(i)==i) kuai++; else
{
if (b[1][gf(i)]==b[1][i]) bj[i]=0;
}
}
ans=qans(r)-qans(l-1);
printf("%lld\n",ans);
return 0;
}