P3220 [HNOI2012]与非

    • 111通过
    • 433提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 位运算,按位 并查集 构造 2012 湖南
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    如果你能提供题面或者题意简述,请直接在讨论区发帖,感谢你的贡献。

    题目描述

    NAND(与非)是一种二元逻辑运算,其运算结果为真当且仅当两个输入的布尔值不全为真。NAND运算的真值表如下(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]内可以被计算出的数的个数

    输入输出样例

    输入样例#1: 复制
    3  3 1 4
    3  4 5
    输出样例#1: 复制
    4

    说明

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

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。