堪称bitset神题

思路

考虑最朴素的做法：暴力计算每一个集合。但是直接计算会MLE+TLE。注意到每一个数在一个集合中只有出现于不出现两种状态，考虑bitset优化。

但是如果直接在主函数外定义bitset<50010>s[450010]会直接报错，无法编译，只能在主函数内定义bitset<50010>s[n+m+1]这不会报错，同时还要感谢题目的5120MiB的内存。

至于复杂度，理论上是$O(NM)$的，但是由于有bitset优化，只有$O(\frac{NM}{w})$，常数复杂度约为625000000，过这道题还是太富裕了。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10,M=4e5+10;
int n,m;
int main()
{
	int q;scanf("%d%d%d",&n,&m,&q);
	bitset<N>s[n+m+1];
	for(int i=1;i<=n;i++)for(int j=i;j<=n;j+=i)
	{
		s[i][j]=1;
	}
	for(int i=1,op,x,y;i<=m;i++)
	{
		scanf("%d%d",&op,&x);
		if(op==1)
		{
			scanf("%d",&y);
			s[n+i]=s[x]|s[y];
		}
		if(op==2)
		{
			scanf("%d",&y);
			s[n+i]=s[x]&s[y];
		}
		if(op==3)
		{
			s[n+i]=~s[x];
		}
	}
	while(q--)
	{
		int x,y;scanf("%d%d",&x,&y);
		if(s[x][y])puts("TAK");
		else puts("NIE");
	}
	return 0;
}