P9393 紫丁香题解

FFTotoro · 2026-01-23 17:36:46 · 题解

提供一种与其他题解不同的处理方法。

操作的性质看起来不怎么样，正难则反，套路地考虑如果倒过来操作会怎样（以下称其为“逆操作”）：对于一个询问 S，尝试从高位到低位依次确定答案的该位是否可以为 \texttt{1}——即给定一个数 X，问 X 通过若干次逆操作能否变为 S 的子集。

如果对一个二进制数 X 进行逆操作 T_i，则必须满足的条件是“X 中的所有 \texttt{1} 在 T_i 的对应位置为 \texttt{1} 或 \texttt{-}”。在逆操作的过程中，对于 X 中和 T_i 中均为 \texttt{1} 的位置，在之后的逆操作中 X 这一位是否为 \texttt{1} 并不重要（因为被这次操作覆盖了）；也就是说，考虑二进制数 C_i 满足其第 j 位为 \texttt{1} 当且仅当 T_{i,j}=\texttt{-}，则可以执行 X\gets X\operatorname{and}C_i。

显然不能对于每个二进制数都做一遍所有能做的逆操作（这样的枚举量是 O(nq) 的）。对于逆操作 T_i，考虑二进制数 S_i 满足其第 j 位为 \texttt{1} 当且仅当 T_{i,j}\ne\texttt{0}，则所有可以进行 T_i 的二进制数刚好是 S_i 的所有子集。构造数组 a_0,a_1,\ldots,a_{2^m}，初始时令 a_i=2^m-1，每考虑到一个逆操作 T_i 就执行 a_{S_i}\gets a_{S_i}\operatorname{and}C_i。最后做一遍高维后缀 \operatorname{and} 得到 a'，a'_i 的含义即为：对于二进制数 i，只进行 i 可以进行的逆操作，i 最小可以变成多少。

于是最终的操作过程必然形如：X\to a'_X\to a'_{a'_X}\to\cdots，直到不能进行操作。所以再对于 i=0,1,\ldots,2^m 分别执行 a'_i\gets a'_{a'_i} 得到 a''_i，即为 i 最终可以变成的最小值。

最后对于每个询问按照文章开头描述的方法进行求解。时间复杂度 O((n+q+2^m)m)。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int m,n,q; cin>>m>>n>>q;
  vector<int> a(1<<m);
  iota(a.begin(),a.end(),0);
  for(int i=0;i<n;i++){
    string t; cin>>t;
    int s=0,c=0;
    for(char j:t)(s<<=1)|=j!='0',(c<<=1)|=j=='-';
    a[s]&=c;
  } // 考虑每次逆操作的影响
  for(int S=(1<<m)-1;~S;S--)
    for(int i=0;i<m;i++)
      if(!(S>>i&1))a[S]&=a[S|1<<i]; // 高维后缀 and
  for(auto &x:a)x=a[x];
  while(q--){
    string t; cin>>t;
    int w=0,s=0;
    for(char i:t)(w<<=1)|=i&1;
    for(int i=m-1;~i;i--)
      cout<<((a[s|1<<i]|w)==w?(s|=1<<i,1):0); // 类似二分的过程
    cout<<'\n';
  }
  return 0;
}

P9393 紫丁香 题解

P9393 紫丁香题解