题解 | F

这种问题先考虑和答案顺序有没有关系，每个点的开关灯状态只和当前点被操作次数的奇偶性和本身初始状态有关，所以跟答案顺序无关

，可以把状态压到 __int128 或者 bitset 里面，我们考虑把对于每个灯操作一次，他能影响到的其他灯也状压下来，记为 ，所有灯的初始状态记为 ，那其实最后就是要求一个集合 ，使得 ，其中 代表最后全开的状态

询问一个序列的一些数异或值是否存在，考虑使用线性基维护，核心代码如下 :

#define iint __int128
const int N=100+10;
int T=1,n,m;
int x[N],y[N];
iint mask;
pair<iint,set<int> > p[N];

void insert(iint x,int pos){
	bool f=0;
	set<int> now;
	now.insert(pos);
	for(int i=n-1;i>=0;i--)
		if(x&(((iint)1<<i))){
			if(p[i].first){
				x^=p[i].first;
				for(auto t: p[i].second){
					if(now.count(t)) now.erase(t);
					else now.insert(t);
				}
			}
			else{ p[i].first=x,p[i].second=now;break ;}
		}
	return ;
}
void solve(){
	n=read();
	for(int i=0;i<n;i++){
		char c=getchar();int res=c-'0';
		if(!res) mask|=((iint)1<<i);
	}
	for(int i=1;i<=n;i++) x[i]=read(),y[i]=read();
	for(int i=1;i<=n;i++){
		iint res=0;
		for(int j=1;j<=n;j++) if(x[i]==x[j] || y[i]==y[j]) 
			res|=((iint)1<<(j-1));
		insert(res,i);
	}
	set<int> ans;
	for(int i=n-1;i>=0;i--){
		if((mask&((iint)1<<i))==0) continue ; 
		if(p[i].first){
			mask^=p[i].first;
			for(auto t: p[i].second){
				if(ans.count(t)) ans.erase(t);
				else ans.insert(t);
			}
		}else return puts("-1"),void();
	}
	printf("%d\n",ans.size());
	for(auto t: ans) printf("%d ",t);
	return ;
}