D. Love-Hate

思路：
如果知道答案是某个人的子集以及这个人的编号，那么能不能算出答案，以及时间复杂度是多少，然后考虑到 生日悖论 ，因为答案是 个人的子集，所以我们任意选一个人 ，答案不是 的子集的概率是 （实际更小），那么我们只要取 30 个人，这些人的子集都不包含答案的概率就小到，几乎可以认为不可能发生。

状压求每个子集有多少人喜欢，这些子集其实是和不喜欢的货币是没关系的，所以可以离散化，存所有喜欢的货币，然后把它们离散化为。表示第个人和喜欢的货币的最大交集（状压），先存下，然后通过一种货币来状态转移，比如：。
代码中状态转移的两层循环不能对调位置，一定要先枚举某一位，然后再枚举每个状态，这样才能保证后面的状态不被重复计算。

用mt19937 read(time(0));时不能关流。注意所有人喜欢的货币集合小于30的情况，防止死循环。

MyCode:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e4 + 7, maxm = 2e5 + 7;
mt19937 read(time(0));
int f[maxn],cnt[maxn],mx;
string ans,s[maxm];
map<string,bool>vis;
set<string>ft;
vector<int>pos;
int main() {
//    ios::sync_with_stdio(false);
//    cin.tie(0),cout.tie(0);//
    int n,m,p;
    cin>>n>>m>>p;
    for(int i=1;i<=n;++i) cin>>s[i],ft.insert(s[i]);
    string e(m,'0');
    ans=e;
    int end=1<<p;
    for(int i=0;i<end;++i) cnt[i]=cnt[i-(i&-i)]+1;
    uniform_int_distribution<int>lim(1,n);
    for(int cas=min((int)ft.size(),30);cas;--cas) {
        int x=lim(read);
        while(vis[s[x]]) x=lim(read);
        vis[s[x]]=true;
        pos.clear();
        for(int i=0;i<m;++i)
            if(s[x][i]=='1') pos.emplace_back(i);
        memset(f,0,sizeof f);
        for(int i=1;i<=n;++i) {
            int tmp(0);
            for(int j:pos) {
                tmp<<=1;
                if(s[i][j]=='1') tmp|=1;
            }
            ++f[tmp];
        }
        end=1<<pos.size();
        for(int i=0;i<pos.size();++i)
            for(int j=1;j<end;++j) 
                if(j&(1<<i)) f[j^(1<<i)]+=f[j];
        for(int i=1;i<end;++i) if(f[i]*2>=n&&cnt[i]>cnt[mx]) {
            mx=i;
            ans=e;
            for(int j=pos.size()-1,k=i;~j;--j,k>>=1) if(k&1) 
                ans[pos[j]]='1';
        }
    }
    cout<<ans<<'\n';
    return 0;
}