I solved this problem using a method similar to ‘search pruning’. I found that the expected complexity of this method is guaranteed by running the code.
How can I prove it mathematically rigorous?
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
struct{int s[2];}t[maxn * 64];
int tot;
void ins(unsigned long long x){for(int i=64,u=0;~--i;u=t[u].s[x>>i&1]?:t[u].s[x>>i&1]=++tot);}
void dfs(int u,int v,int _d){
if(!_d)cout<<"YES",exit(0);
for(int c:{0,1})for(int d:{0,1})
if(!(c&d))if(t[u].s[c]&&t[v].s[d])
dfs(t[u].s[c],t[v].s[d],_d-1);
}
int main() {
mt19937_64 rng(random_device{}());
int n;cin>>n;
for(int i=1;i<=n;++i)ins(rng());
dfs(0,0,64);cout<<"NO";
}