当前位置: 代码迷 >> 综合 >> 洛谷4424 [HNOI/AHOI2018]寻宝游戏
  详细解决方案

洛谷4424 [HNOI/AHOI2018]寻宝游戏

热度:63   发布时间:2023-12-14 16:20:17.0

标签:智商题,位运算,数论

题目

题目传送门

题目描述

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

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

很快,在最新的一期的Voo Doo杂志上,你发现了 q q q个长度也为 m m m的二进制数 r 1 , r 2 , . . . , r q r_1,r_2,...,r_q r1?,r2?,...,rq?

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

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

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

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

输入输出格式

输入格式

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

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

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

输出格式

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

输入输出样例

输入样例#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 ≤ 20 , m ≤ 30 , q = 1 n \le 20, m \le 30, q = 1 n20,m30,q=1

对于另外 20 的数据, n ≤ 1000 , m ≤ 16 n \le 1000, m \le 16 n1000,m16

对于另外 40 的数据, n ≤ 500 , m ≤ 1000 n \le 500, m \le 1000 n500,m1000

对于全部的数据 1 ≤ n ≤ 1000 , 1 ≤ m ≤ 5000 , 1 ≤ q ≤ 1000 1≤n≤1000,1≤m≤5000,1≤q≤1000 1n1000,1m5000,1q1000

分析

本题膜了一波题解,思路真的好妙啊qwq

考虑将操作序列转化为01序列

可以将 ∨ ∨ 视为0, ∧ ∧ 视为1

结论:如果i前面的运算符和第j位相同那么运算结果就不会改变

转化之后发现就是要求操作序列(用二进制表示)<x

转化为二进制序列比大小

ans=最小的结果为1的01串-最大的结果为0的01串

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
    ll f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
    x=x*10+ch-'0';ch=getchar();}return x*f;
}
//**********head by yjjr**********
const int maxn=5e3+6,mod=1e9+7;
int n,m,q,c[2],up,dw,a[maxn],b[maxn],s[maxn],t[maxn],qp[maxn];
char st[maxn];
int main()
{
    n=read(),m=read(),q=read();qp[1]=1;rep(i,2,n+1)qp[i]=(qp[i-1]<<1)%mod;rep(i,1,m)a[i]=i;rep(i,1,n){
    scanf("%s",st+1);c[0]=0,c[1]=m;rep(j,1,m)st[j]=='1'?s[j]=(s[j]+qp[i])%mod:++c[0];dep(j,m,1)b[c[st[a[j]]-48]--]=a[j];swap(a,b);}rep(i,1,m)t[i]=s[a[i]];t[m+1]=qp[n+1];while(q--){
    scanf("%s",st+1);up=m+1,dw=0;dep(i,m,1)if(st[a[i]]=='0'){
    dw=i;break;}rep(i,1,m)if(st[a[i]]=='1'){
    up=i;break;}printf("%d\n",up<dw?0:(t[up]-t[dw]+mod)%mod);}return 0;
}