网络最大流

大概是最劣解？但能过嘿嘿。

考虑到对 $b$ 中某个值进行操作的时候能取到的值不多大概是 $O(\log^2)$ 种，所以想办法处理出这些数然后跟 $a$ 里面的数匹配，匹配的话当然是建图跑最大流就好啦。

很遗憾，tle on test 30 ，考虑剪枝：

  1. 集合 $a$ 和 $b$ 中重复的取值压倒一个点里面去，然后流量改成这个取值的数量。
  2. 考虑到一个数二进制末尾有 $0$ 时，把这些 $0$ 干掉不影响存在 $b$ 中的值与其匹配，所以直接把二进制末尾的 $0$ 全部干掉就好啦，然后发现边数从 $O(\log^2)$ 变成了 $O(\log)$ 的。
  3. 尝试指令集，或更优的网络流模型。

最重要的还是第 $2$ 个优化，点数 $O(n)$，边数 $O(n\log n)$，卡过去了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
#define rep(a,b,c) for(int c(a);c<=(b);++c)
#define grep(b,c) for(int c(head[b]);c;c=Nxt[c])
using std::vector;using std::map;
inline void print(const int &p){if(p>9)print(p/10);putchar(p%10+'0');}
inline int read()
{
	int res=0;char ch=getchar();bool flag=0;
	while(ch<'0'||ch>'9')flag^=(ch=='-'),ch=getchar();
	while(ch<='9'&&ch>='0')res=res*10+(ch^48),ch=getchar();
	return flag ? -res : res ;
}
struct Pair
{
	int x,y;inline Pair(int X=0,int Y=0){x=X;y=Y;}
	inline bool operator < (const Pair &Q)const {return x==Q.x?y<Q.y:x<Q.x;}
};
namespace MF
{
	const int N=2e6+10,M=1e7+10,INF=0x3f3f3f3f;
	int head[N],des[M],Nxt[M],cgt=1,s,t,S,dep[N],que[N],cap[M],H,T,h2[N];bool vis[N];
	inline void Clear(){memset(head,0,(S+2)<<2);cgt=1;S=0;}
	inline void ins(const int &x,const int &y,const int &c=1)
	{
		if(!x||!y)return;
		Nxt[++cgt]=head[x];des[head[x]=cgt]=y;cap[cgt]=c;
		Nxt[++cgt]=head[y];des[head[y]=cgt]=x;cap[cgt]=0;
	}
	inline bool bfs()
	{
		memset(dep,0,(S+2)<<2);dep[que[H=T=0]=s]=1;
		while(H<=T){int u=que[H++];grep(u,i)if(cap[i]&&!dep[des[i]])dep[que[++T]=des[i]]=dep[u]+1;} return dep[t];
	}
	inline int dfs(const int &u=s,int in=INF)
	{
		if(u==t)return in;int out=0;
		for(int &i=h2[u];i;i=Nxt[i])
		{
			int v=des[i];if(cap[i]&&dep[v]==dep[u]+1)
			{
				int tmp=dfs(v,cap[i]<in?cap[i]:in);
				out+=tmp;cap[i]-=tmp;cap[i^1]+=tmp;if(!(in-=tmp))break;
			}
		}
		return out?out:dep[u]=0;
	}
	inline int dinic()
	{
		int res=0;while(bfs())memcpy(h2,head,(S+2)<<2),res+=dfs();return res;
	}
	inline void Init(){memset(head,0,(S+2)<<2);S=0;cgt=1;} 
}
using MF::ins;using MF::S;using MF::s;using MF::t;
const int N=2e5+10;int n;map<int,Pair>mp;map<int,int> b;
inline void Solve()
{
	n=read();s=++S;t=++S;mp.clear();int cc=0;b.clear();
	rep(1,n,i)
	{
		int x=read();if(__builtin_popcount(x)==1){++cc;continue;}
		while(!(x&1))x>>=1;Pair &q=mp[x];++q.x;if(q.x==1)q.y=++S;
	}
	rep(1,n,i)++b[read()];
	for(std::pair<int,int> v: b)
	{
		int x=v.first,id=++S;ins(s,id,v.second);
		rep(0,30,i)if(x>>i&1)
		{
			int cur=x>>i;
			if(__builtin_popcount(cur)==1)break;
			if(mp.count(cur))
			{
				ins(id,mp[cur].y,v.second);
			}
		}
	}
	for(std::pair<int,Pair> v:mp)
	{
		Pair tmp=v.second;
		ins(tmp.y,t,tmp.x);
	}
	puts(MF::dinic()==n-cc?"YES":"NO");
	MF::Init();
}
int main()
{
	int T=read();while(T--)Solve();
}