Problem

http://uoj.ac/problem/384

Solution

神奇的类比与推理
https://kelin.blog.luogu.org/solution-p4424

注意 lo 与 up 的一些特殊情况。
不要忘记判断

Code

#include<bits/stdc++.h>
#define MOD (1000000007ll)
using namespace std;

const int N=1010, M=5010;
typedef bitset<N> bs;
bs x[M];
int id[M], li[M], rk[M], pl[N], t[M];
bool operator < (const bs &a, const bs &b) {
    for(int i=N-1;i>=0;i--)
        if(a[i]!=b[i]) return a[i]<b[i];
    return 0;
}
bool cmp(const int &a, const int &b) { return x[a]<x[b]; };

int main() {
    pl[0]=1; for(int i=1;i<N;i++) pl[i]=1ll*pl[i-1]*2%MOD;
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m, q;
    cin>>n>>m>>q;
    char ch;
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
        cin>>ch, t[j]=(t[j]+1ll*(x[j][i]=ch-'0')*pl[i])%MOD;
    for(int i=0;i<m;i++) id[i]=i;
    sort(id, id+m, cmp);
    for(int i=0;i<m;i++) rk[id[i]]=i;
    int lo, up;
    t[m+1]=1ll*pl[n]+MOD%MOD;
    id[m]=m, id[m+1]=m+1;
    while(q--) {
        lo=m, up=m+1;
        for(int i=0;i<m;i++) cin>>ch, li[rk[i]]=ch-'0';
        for(int i=m-1;i>=0;i--) if(!li[i]) { lo=i; break; }
        for(int i=0;i<m;i++) if(li[i]) { up=i; break; }
        if(lo!=m && up<lo) cout<<0<<'\n';
        else cout<<(1ll*t[id[up]]-t[id[lo]]+MOD)%MOD<<'\n';
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-hnoi-2018-hunt.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆