洛谷题面

题目大意

有 \(n\) 个开关和 \(m\) 个灯泡，每个开关都处于“开”和“关”状态中的一种。开关从 \(1\) 到 \(n\) 编号，灯泡从 \(1\) 到 \(m\) 编号。

\(i\) 号灯泡连接着 \(k_i\) 个开关：开关 \(s_{i,1},s_{i,2},\cdots,s_{i,k_i}\)。当这些开关中，处于“开”状态的开关数量之和模 \(2\) 余 \(p_i\) 时，这个灯泡就会被点亮。

有多少“开”和“关”的组合，可以点亮所有灯泡？

题目分析

考虑 \(\rm dfs\)。

我们令 \(1\) 表示“开”，\(0\) 表示“关”，我们照常开一个 \(\rm a\) 数组来记录枚举的状态。

如果状态枚举到最后了，已经枚举完一个完整的状态了，我们对枚举的状态进行一次检验即可。如果有一个灯泡不满足条件，那么直接回溯；如果全部满足条件，方案数加一并回溯继续枚举。

时间复杂度 \(\operatorname{O}(2^n nm)\)。

极限情况 \(2^{10}\times 10\times 10=102400\)，一秒内可以跑过。

代码

//2021/11/13

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <cstdio>

#include <climits>//need "INT_MAX","INT_MIN"

#define enter() putchar(10)

#define debug(c,que) cerr<<#c<<" = "<<c<<que

#define cek(c) puts(c)

#define blow(arr,st,ed,w) for(register int i=(st);i<=(ed);i++)cout<<arr[i]<<w;

#define speed_up() std::ios::sync_with_stdio(false)

namespace Newstd
{
	inline int read()
	{
		char c;
		bool flag=false;
		while((c=getchar())<'0' || c>'9')
		{
		    if(c=='-') flag=true;
		}
		int res=c-'0';
		while((c=getchar())>='0' && c<='9')
		{
		    res=(res<<3)+(res<<1)+c-'0';
		}
		return flag?-res:res;
	}
	inline void print(int x)
	{
		if(x<0)
		{
			putchar('-');x=-x;
		}
		if(x>9)
		{
			print(x/10);
		}
		putchar(x%10+'0');
	}
}

using namespace Newstd;

using namespace std;

const int ma=15;

int a[ma],p[ma],k[ma];

int mp[ma][ma];

int n,m;

int ans;

inline void dfs(int step)
{
	if(step>n)
	{
		for(register int i=1;i<=m;i++)
		{
			int tmp=0;
			
			for(register int j=1;j<=k[i];j++)
			{
				tmp+=a[mp[i][j]];
			}
			
			if(tmp%2!=p[i])
			{
				return;
			}
		}
		
		ans++;
		
		return;
	}
	
	a[step]=1;
	
	dfs(step+1);
	
	a[step]=0;
	
	dfs(step+1);
}

int main(void)
{
	n=read(),m=read();
	
	for(register int i=1;i<=m;i++)
	{
		k[i]=read();
		
		for(register int j=1;j<=k[i];j++)
		{
			mp[i][j]=read();
		}
	}
	
	for(register int i=1;i<=m;i++)
	{
		p[i]=read();
	}
	
	dfs(1);
	
	printf("%d\n",ans);
	
	return 0;
}