[Bzoj5285][洛谷P4424][HNOI/AHOI2018]寻宝游戏（bitset）

时间：2023-03-10 00:11:13
[Bzoj5285][洛谷P4424][HNOI/AHOI2018]寻宝游戏（bitset）

P4424 [HNOI/AHOI2018]寻宝游戏

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

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

很快，在最新的一期的Voo Doo杂志上，你发现了qq 个长度也为mm 的二进制数r_1,r_2,...,r_qr1​,r2​,...,rq​ 。

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

保持数组a_1,a_2,...,a_na1​,a2​,...,an​ 的元素顺序不变，你可以在它们之间插入∧∧ （按位与运算）或者∨∨ （按位或运算）。例如：11011∧00111=0001111011∧00111=00011 ，11011∨00111=1111111011∨00111=11111 。

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

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

输入输出格式

输入格式：

第一行三个数nn ,mm ,qq ，含义如题所述。

接下来nn 行，其中第ii 行有一个长度为mm 的二进制数，左边是最高位，表示a_iai​ 。

接下来qq 行，其中第ii 行有一个长度为mm 的二进制数，左边是最高位，表示r_iri​ 。

输出格式：

输出qq 行，每行一个数，其中的ii 行表示对于r_iri​ 的答案。

输入输出样例

输入样例#1： 






输出样例#1：


















输入样例#2： 














输出样例#2： 
















说明




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


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


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


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


分析：




倒着来推，每次枚举每个位置是or 还是 and。设每个串为S[i]，设每次查询的串为G


然后有个表 ：（设当前枚举到第i个字符串的第j位，设F[i][j]表示（1 ~ i - 1）操作后第j位为0/1）


————————————


[Bzoj5285][洛谷P4424][HNOI/AHOI2018]寻宝游戏（bitset）


解释起来也很简单：


比如说在枚举最后一个操作时，我们查询字符串第j位为0，第n个字符串第j位为1，如果选了or操作，无论[1，n - 1]的操作怎么枚举，在 or 1过后，值都只会等于1，不合法，记F[i][j] == -1


比如说在枚举最后一个操作时，我们查询字符串第j位为1，第n个字符串第j位为1，如果选了or操作，无论[1，n - 1]的操作怎么枚举，在 or 1过后，值都会等于1，一定和合法，记F[i][j] == 0/1


比如说在枚举最后一个操作时，我们查询字符串第j位为1，第n个字符串第j位为1，如果选了ang操作，只有当[1，n - 1]的操作枚举使第j位为1时，才有1 & 1 == 1，记F[i][j] == 1


以此类推，推下来发现每次推的F[i][j]除了0/1和-1的状态，其他位都是和原字符串一样的，这样就不用记录F[i][j]，只用记录有哪些位置满足了 0 / 1，记为 t。


Bfs按层枚举深搜树，然后记录每层有哪些合法的 t 状态，按层推下去。复杂度是O(2^n * q *（位运算代价） )


恭喜你，得到10分了


剪枝




-1表示（1~i - 1）的操作怎么枚举都不可能满足。


0/1表示（1 ~ i - 1）的操作随便枚举都可以满足。


这样我们倒着2^n次方枚举所有填的可能，当出现-1就剪枝，当全部位都为0/1就可以直接加上2^（i - 1），并剪枝。


这样剪下来，每一层状态数最多为2，是不是很神奇。。


然后复杂度就变成了O（nq * （位运算代价））。


使用bitset（要手写），把位运算代价优化成5000 / 64 = 78


总复杂度O（78nq）


AC代码：






# include <iostream>

# include <cstdio>

# include <cstring>

using namespace std;

typedef unsigned long long llu;

const int N = ;

const int mod = 1e9 + ;

int block,n,m,Q;

struct bitset{

   llu p[];

   void read()

   {

       memset(p,0llu,sizeof p);

       char i = getchar();

    while(!isdigit(i))i = getchar();

    for(int j = ;j < m;j++,i = getchar())p[j / ] |= (((llu)(i - '')) << (j % ));

   }

   void clear(){for(int i = ;i <= block;i++)p[i] = ;}

}s[N],f[N],nt,t1,t2,v1,v2,g,c1,c2,que[][];

int ret,dt,cur,tot;

llu ans,bac[N];

void init()

{

    block = (m - ) / ;

    bac[] = ;for(int i = ;i <= n;i++)bac[i] = (bac[i - ] << ) % mod;

    memset(nt.p,0llu,sizeof nt.p);

    for(int j = ;j < m;j++)nt.p[j / ] |= (1llu << (j % ));

    for(int i = ;i <= n;i++)

    {

        s[i].read();

        for(int j = ;j <= block;j++)

        f[i].p[j] = s[i].p[j] ^ nt.p[j];

    }

}

int main()

{

  scanf("%d %d %d",&n,&m,&Q);

  init();

  while(Q--)

  {

      g.read();dt = ans = cur = ;que[cur][++dt].clear();

      for(int i = n;i;i--)

      {

          tot = dt;cur ^= ;dt = ;

          for(int j = ;j <= tot;j++)

          {

            bool f1 = true,f2 = true,l1 = true,l2 = true;

            for(int k = ;k <= block;k++)

          {

           if(!f1 && !f2)break;

           if(que[cur ^ ][j].p[k] == nt.p[k])

           {

                if(f1)t1.p[k] = nt.p[k];

                if(f2)t2.p[k] = nt.p[k];

                continue;

           }

           if(f1)v1.p[k] = s[i].p[k] & (s[i].p[k] ^ g.p[k]);

           if(f2)v2.p[k] = g.p[k] & (s[i].p[k] ^ g.p[k]);

           if(f1 && (v1.p[k] & que[cur ^ ][j].p[k]) != v1.p[k])f1 = false;

           if(f2 && (v2.p[k] & que[cur ^ ][j].p[k]) != v2.p[k])f2 = false;

           if(f1)t1.p[k] = que[cur ^ ][j].p[k] | (s[i].p[k] ^ v1.p[k]);

           if(f2)t2.p[k] = que[cur ^ ][j].p[k] | (f[i].p[k] ^ v2.p[k]);

           if(f1 && t1.p[k] != nt.p[k])l1 = false;

           if(f2 && t2.p[k] != nt.p[k])l2 = false;

          }

          if(f1)

          {

              if(l1)ans = (ans + bac[i - ]) % mod;

              else que[cur][++dt] = t1;

          }

          if(f2)

          {

              if(l2)ans = (ans + bac[i - ]) % mod;

              else que[cur][++dt] = t2;

          }

          }

      }

      for(int j = ;j <= dt;j++)

      {

          bool f1 = true;

          for(int k = ;k <= block;k++)

          {

              if((que[cur][j].p[k] ^ nt.p[k]) & g.p[k]){f1 = false;break;}

          }

          ans += f1;

      }

      cout<<ans<<endl;

  }

}


相关文章