LOJ2494. 「AHOI / HNOI2018」寻宝游戏
给出\(n 1\)个长度为\(m\)的二进制数组成的序列（规定\(a_0=0\)，其它读入），每个询问给出一个二进制数。你需要求出在这个序列中每个相邻位置之间添加符号\(\and\)或\(\or\)（规定运算从左往右进行），使得运算结果为询问的二进制数的方案数。
\(n,q\le 1000,m\le 5000\)
没有看到运算顺序所以想了一整个白天甚至浪费了一节物理课
考虑运算加数字接在后面的意义：\(\and 0\)和\(\or 1\)分别表示赋值，剩下两个分别表示保持不变。
于是有个normal的模型转化：从后往前扫，维护个结果\(res\)，一开始每个位置未确定，每次用\(a_i\)中的所有\(0\)或所有\(1\)覆盖\(res\)未确定的位置，要求覆盖的这个位置一定符合询问的数。可以直接暴力做，只要加上每个位置都被覆盖之后就退出的剪枝，就可以做到\(O(\frac{nmq}{\omega})\)的复杂度，出题人没有卡，可以过。（考虑没有确定的位置，假如选了\(0\)，设\(S_0\)表示结果应当\(0\)的位置集合，\(a_{i,0}\)表示\(a_i\)中\(0\)的位置集合，如果\(a_{i,0}\subseteq S_0\)才可以递归下去；选\(1\)同理。进而发现\(a_{i,0}\subseteq S_0 \and a_{i,1}\subseteq S_1\Leftrightarrow (a_{i,0}=S_0)\)，也就是只有\(a_{i,0}=S_0\)时会分叉。注意到分叉之后，没有确定的位置的目标值只有一种（假设为\(0\)），如果选\(1\)那么只有影响到的位置是空集才合法，此时如果选\(0\)就是覆盖全集会被剪枝掉）
正解很妙：
考虑搞出一个操作序列。把\(\and\)视作\(1\)，\(\or\)视作\(0\)。
把\(n\)个\(m\)位数转置变成\(m\)个\(n\)位数。现在对于某个数\(b_i\)，考虑它和\(opt\)的关系会如何决定结果。发现是从后往前，第一个不同的位置。假如这个位置上\(opt\)和\(b_i\)分别为\(0,1\)，那么最终结果是\(1\)；如果是\(1,0\)，或找不到不同的位置，结果是\(0\)。
这其实就是比大小，当\(opt<b_i\)时为\(1\)，否则为\(0\)。
于是对\(b_i\)排序。每次根据询问的值计算出\(opt\)的范围即可。
using namespace std;#include <bits/stdc .h>#define N 1005#define M 5005#define ull unsigned long long#define mo 1000000007int n,m,Q;char str[M];int _b[M][N],*b[M],p[M],v[M];bool cmpb(int x[],int y[]){for (int i=n;i>=1;--i){if (x[i]<y[i]) return 1;if (x[i]>y[i]) return 0;}return 0;}int main(){freopen("in.txt","r",stdin);scanf("%d%d%d",&n,&m,&Q);for (int j=0;j<m; j)b[j]=_b[j];for (int i=1;i<=n; i){scanf("%s",str);for (int j=0;j<m; j)b[j][i]=str[j]-'0';}sort(b,b m,cmpb);for (int j=0;j<m; j){int re=(b[j]-_b[0])/N;p[re]=j;for (int i=n;i>=1;--i)v[j]=(v[j]*2 b[j][i])%mo;}v[m 1]=1;for (int i=1;i<=n; i)v[m 1]=v[m 1]*2%mo;while (Q--){scanf("%s",str);int l=-1,r=m 1;for (int j=0;j<m; j)if (str[j]=='1')r=min(r,p[j]);elsel=max(l,p[j]);printf("%d\n",l<r?(v[r]-(l>=0?v[l]:0) mo)%mo:0);}return 0;}