抽象化题意：
一共有 \(m\) 个元素，给定 \(n\) 个集合，每个集合的元素不超过 \(15\) 个，求出一个元素个数最多的集合 \(S\) 是至少 \(\lceil \dfrac{n}{2} \rceil\) 个集合的子集。
其中$ p $ $ (1 \le n \le 2 \cdot 10^5, 1 \le p \le m \le 60) $
我们先假设 \(limit= \lceil \dfrac{n}{2} \rceil\)
先考虑最基础的暴力，如果我们每次枚举答案集合 \(S\) ，然后再计算出是否有大于等于 \(limit\) 个集合是 \(S\) 的超集，更新答案
计算超集可以通过 \(SOSDP\) ，仍然TLE，先从题目本质入手，它是让我们求一个集合使得是至少 \(\lceil \dfrac{n}{2} \rceil\) 个集合的子集，那么这个答案显然是某 \(\lceil \dfrac{n}{2} \rceil\) 个集合的子集，那如果我们随机任取一个集合，正确答案是它子集的概率就是50%，那我们直接随 \(num\) 次，可以直接让答案错误的概率降到极低，错误的概率就是 \(\dfrac{1}{2^{num}}\) 。
也就是说随机50次的样子，每次对于随机到的集合，通过 \(O(p\times2^p)\) 来计算超集，具体细节就是需要搞个vector来存某位是1的位置就行了。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
template<class T>
inline T read(){
T r=0,f=0;
char c;
while(!isdigit(c=getchar()))f|=(c=='-');
while(isdigit(c))r=(r*10)+(c^48),c=getchar();
return f?-r:r;
}
int n,m,p,limit;
int a[200005];
bool flag[200005];
vector<int>g;
inline int idx(char c){
return c-'0';
}
int dp[1000005];
int ans;
mt19937 rd(time(0));
inline void work(){
int pos;
while(1){
pos=rd()%n+1;
if(!flag[pos]){flag[pos]=true;break;}
}
g.clear();
int num=a[pos];
for(int i=0;i<m;i++){
if((num>>i)&1)g.emplace_back(i);
}
memset(dp,0,sizeof(dp));
int S=g.size();
for(int i=1;i<=n;i++){
int tmp=0;
for(int j=0;j<S;j++){
if((a[i]>>g[j])&1)tmp|=(1<<j);
}
++dp[tmp];
}
for(int i=0;i<S;i++){
for(int j=0;j<(1ll<<S);j++){
if(!((j>>i)&1))dp[j]+=dp[j^(1<<i)];
}
}
int res=0;
for(int i=1;i<(1ll<<S);i++){
if(dp[i]>=limit){
if(__builtin_popcountll(res)<__builtin_popcountll(i))res=i;
}
}
int res2=0;
for(int i=0;i<S;i++){
if((res>>i)&1)res2|=(1ll<<g[i]);
}
if(__builtin_popcountll(res)>__builtin_popcountll(ans))ans=res2;
}
signed main(){
n=read<int>(),m=read<int>(),p=read<int>();
limit=(n+1)>>1;
for(int i=1;i<=n;i++){
char c;
for(int j=0;j<m;j++){
cin>>c;
if(idx(c))a[i]|=(1ll<<j);
}
}
for(int t=1;t<=min(n,50ll);t++)work();
for(int i=0;i<m;i++)
((ans>>i)&1)?putchar('1'):putchar('0');
puts("");
return 0;
}