P4424 [HNOI/AHOI2018]寻宝游戏

    • 348通过
    • 1.1K提交
  • 题目提供者 M_sea
  • 评测方式 云端评测
  • 标签 位运算,按位 排序 进制 各省省选 2018 安徽 湖南 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 512MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    某大学每年都会有一次Mystery Hunt的活动,玩家需要根据设置的线索解谜,找到宝藏的位置,前一年获胜的队伍可以获得这一年出题的机会。

    作为新生的你,对这个活动非常感兴趣。你每天都要从西向东经过教学楼一条很长的走廊,这条走廊是如此的长,以至于它被人戏称为infinite corridor。一次,你经过这条走廊时注意到在走廊的墙壁上隐藏着$n$个等长的二进制的数字,长度均为$m$。你从西向东将这些数字记录了下来,形成一个含有$n$个数的二进制数组$a_1,a_2,...,a_n$。

    很快,在最新的一期的Voo Doo杂志上,你发现了$q$个长度也为$m$的二进制数$r_1,r_2,...,r_q$。

    聪明的你很快发现了这些数字的含义。

    保持数组$a_1,a_2,...,a_n$的元素顺序不变,你可以在它们之间插入$∧$(按位与运算)或者$∨$(按位或运算)。例如:$11011∧00111=00011$,$11011∨00111=11111$。

    你需要插入$n$个运算符,相邻两个数之前恰好一个,在第一个数的左边还有一个。如果我们在第一个运算符的左边补入一个0,这就形成了一个运算式,我们可以计算它的值。与往常一样,运算顺序是从左到右。有趣的是,出题人已经告诉你这个值的可能的集合——Voo Doo杂志里的那些二进制数$r_1,r_2,...,r_q$,而解谜的方法,就是对$r_1,r_2,...,r_q$中的每一个值$r_i$,分别计算出有多少种方法填入这$n$个计算符,使的这个运算式的值是$r_i$。

    然而,infinite corridor真的很长,这意味着数据范围可能非常大。因此,答案也可能非常大,但是你发现由于谜题的特殊性,你只需要求答案模1000000007的值。

    输入输出格式

    输入格式:

    第一行三个数$n$,$m$,$q$,含义如题所述。

    接下来$n$行,其中第$i$行有一个长度为$m$的二进制数,左边是最高位,表示$a_i$。

    接下来$q$行,其中第$i$行有一个长度为$m$的二进制数,左边是最高位,表示$r_i$。

    输出格式:

    输出$q$行,每行一个数,其中的$i$行表示对于$r_i$的答案。

    输入输出样例

    输入样例#1: 复制
    5 5 1
    01110
    11011
    10000
    01010
    00100
    00100
    输出样例#1: 复制
    6
    输入样例#2: 复制
    10 10 3
    0100011011
    0110100101
    1100010100
    0111000110
    1100011110
    0001110100
    0001101110
    0110100001
    1110001010
    0010011101
    0110011111
    1101001010
    0010001001
    输出样例#2: 复制
    69
    0
    5

    说明

    对于 10% 的数据,$n \le 20, m \le 30, q = 1$

    对于另外 20 的数据,$n \le 1000, m \le 16$

    对于另外 40 的数据,$n \le 500, m \le 1000$

    对于全部的数据$1≤n≤1000,1≤m≤5000,1≤q≤1000$。。

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