LOJ2351_JOI2018Final 毒蛇越狱_毒蛇の出走_Snake Escaping 题解

题意

给你 个长为 的 串，第 个串为 的二进制表达，每个串有权值 。 次询问，每次给你一个长为 的串，其由 构成。求将 换成任意的 之后，所有 可能与给定的询问串相同的串 的权值之和。

题解

本文中的 分别表示二进制与运算，二进制或运算。

考虑一个给定的询问串。

记 分别表示 在询问串的个数， 表示询问串中 的位置，如 ，询问串为 ，则 。由于 ，所以 ，对这三种情况分类讨论。

• 若

  直接暴力枚举每一个 填什么，给总答案加上对应的 串的权值。时间复杂度 。

• 若

  记 。此时：

  • 若 ，则答案为 。
  • 若 ，则答案为 ，即用钦定 的所有位置填 的方案数减去本来是 的位置填了 的方案数。

  这启示我们考虑容斥，用钦定 的位置填 的方案数，减去 的位置填了 的方案数。因为 所以直接枚举哪些本来是 的位置填了 即可，即枚举 的子集。即答案为：
  
  时间复杂度 。

• 若

  同 ，记 ，即 表示所有串 满足其所有 的位置构成的集合是 中 的位置构成的集合的超集的串 的权值和，则答案为：
  
  时间复杂度 。

综上所述，单次询问的时间复杂度为 ，考虑上述的 实际上就是一个高维前缀和，预处理的时间复杂度为 ，所以总时间复杂度为 ，可以通过。

AC 记录及 Code。