P9393 紫丁香-JZTXT

膜拜 yxcat
考虑二分答案，将问题转换成验证 \(A\) 是否由 \(S\) 通过若干次操作生成
将操作效果反向，即存在一个操作 \(x\)，满足 \(A_i=1\) 且 \(x_i=1\)，那么将 \(A_i\) 处的 \(1\) 消掉,
也就是对于一个串 \(A\)，如果 \(A\) 尽量消 \(1\) 之后剩下的消不掉的 \(1\) 正好在 \(S\) 串中该位置也是 \(1\)，那么 \(A\) 合法
令 \(f[s]\) 表示 \(s\) 通过若干次操作剩下消不掉的 \(1\) 的并
令 \(g[s]\) 表示由 \(s\) 通过若干次操作可以删去的 \(1\) 的并
有转移 \(f[s]=f[s\space xor\space g[s]]\)
\(g[s]\) 作高维后缀或
对于最终答案 \(A\) 按位贪心
如果该位可以取 \(1\)，原答案也就是加上这一位上的 \(1\) 后，消不掉的 \(1\) 仍全出现在 \(S\) 里，那么该位就保留 \(1\)。