#PQJ55x6237. QOJ 55_6237

    ID: 3010 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:AHOI 2018动态规划

QOJ 55_6237

第1 题:寻宝游戏(hunt),运行时限1s,内存上限512M,100 分。

【问题描述】 某大学每年都会有一次Mystery Hunt 的活动,玩家需要根据设置的线索解谜,找到宝藏的位置, 前一年获胜的队伍可以获得这一年出题的机会。 作为新生的你,对这个活动非常感兴趣。你每天都要从西向东经过教学楼一条很长的走廊,这条 走廊是如此的长,以至于它被人戏称为infinite corridor。一次,你经过这条走廊的时候,注意到在走廊 的墙壁上隐藏着𝑛个等长的二进制的数字,长度均为𝑚。你从西向东将这些数字记录了下来,形成一个 含有𝑛个数的二进制数组a1,a2,…,an。 很快,在最新的一期Voo Doo 杂志上,你发现了𝑞个长度也为𝑚的二进制串r1,r2,…,rq。 聪明的你很快发现了这些数字的含义。 保持数组a1,a2,…,an 的元素顺序不变,你可以在它们之间插入∧(按位与运算)或者∨(按位或运 算)两种二进制运算符。例如:11011∧00111=00011,11011∨00111=11111。 你需要插入恰好𝑛个运算符,相邻两个数之间恰好一个,在第一个数的左边还有一个。如果我们 在第一个运算符的左边补入一个0,这就形成了一个运算式,我们可以计算它的值。与往常一样,运 算顺序是从左往右。有趣的是,出题人已经告诉你这个值的可能的集合——Voo Doo 杂志里的那一些 二进制数r1,r2,…,rq,而解谜的方法,就是对r1,r2,…,rq 中的每一个值ri,分别计算出有多少种方法填入 这𝒏个运算符,使得这个运算式的值是ri。 然而,infinite corridor 真的很长,这意味着数据范围可能非常大。因此,答案也可能非常大,但是 你发现由于谜题的特殊性,你只需要求答案模1000000007(109 + 7,一个质数)的值。

【程序文件名】 源程序文件名为hunt.cpp/c/pas。

【输入格式】 输入文件名为hunt.in。 第一行三个数𝑛, 𝑚, 𝑞,含义如题所述。 接下来𝑛行,其中第𝑖行有一个长度为𝑚的二进制串,左边是最高位,表示𝑎𝑖。 接下来𝑞行,其中第i 行有一个长度为𝑚的二进制串,左边是最高位,表示ri。

【输出格式】 输出文件名为hunt.out。 输出𝑞行,每行一个数,其中第i 行表示对应于ri的答案。

【输入输出样例1】 hunt.in hunt.out 5 5 1 01110 11011 10000 01010 00100 00100 6

【样例解释1】 有以下且仅有以下六个运算式的值是001002:(下标2 表示被标识的数是二进制数) 0 ∧ 011102 ∧ 110112 ∨ 100002 ∧010102 ∨001002 0 ∨ 011102 ∨110112 ∧ 100002 ∧010102 ∨001002 0 ∧ 011102 ∨110112 ∧ 100002 ∧010102 ∨001002 0 ∨ 011102 ∧ 110112 ∧ 100002 ∧ 010102 ∨001002 0 ∧ 011102 ∧110112 ∧ 100002 ∧010102 ∨001002 0 ∨ 011102 ∨110112 ∨ 100002 ∨010102 ∧001002

【输入输出样例2】 hunt.in hunt.out 10 10 3 0100011011 0110100101 1100010100 0111000110 1100011110 0001110100 0001101110 0110100001 1110001010 0010011101 0110011111 1101001010 0010001001 69 0 5

【数据范围】 对于10%的数据,𝑛≤20, 𝑚≤30, 𝑞= 1 对于另外20%的数据,𝑛≤1000,𝑚≤16 对于另外40%的数据,𝑛≤500, 𝑚≤1000 对于100%的数据,1 ≤𝑛≤1000, 1 ≤𝑚≤5000, 1 ≤𝑞≤1000

【提示】 输入文件可能很大,请注意读入效率。

【编译命令】 对于c++语言: g++ -o hunt hunt.cpp –lm 对于c 语言: gcc -o hunt hunt.c –lm 对于pascal 语言: fpc hunt.pas