jzo3059 雕塑

题目大意

链接
有一个$n\ast n$的网格，你需要选出其中不同行同列的n个点。但其中有m个点不能选择，求一共有多少种方案。
其中$n\le 20,m\le 10$

解题思路

如果不加上其中m个点不能选的规则，那么这题就是一个简单的全排列问题。考虑容斥，最终方案即为合法的方案数减去不合法的方案数。观察$m$的大小，最多只有10，因此我们可以用$2^x$次方求出$n$个点中选择了$x$个不能选的点（$x\le m$）。再减去它们。
另外当我们求出了选择了1个m中的点的方案数并把它们减去之后，实际上也把选择了2个m中的点的方案数减去了，因此我们需要把选择了2个点的方案加回来，这样做又把选择了3个点的方案加上了，因此我们需要把3个点的方案减去……最后我们发现，如果当前的x为奇数，我们就要减去选择x个点的方案，如果是偶数就加上选择x个点的方案。

代码

#include
using namespace std;
int n,m;
long long k[25],s,ans=1;
struct node{
	int x,y;
}a[25];
bool fx[25],fy[25];
void dfs(int dep,int x,int k)
{
	if(x==k)
	{
		s++;
		return;	
	}
	if(dep>m) return;
	if(!fx[a[dep].x]&&!fy[a[dep].y])
	{
		fx[a[dep].x]=fy[a[dep].y]=1;
		dfs(dep+1,x+1,k);
		fx[a[dep].x]=fy[a[dep].y]=0;
	}
	dfs(dep+1,x,k);
}
int main()
{
	cin>>n>>m;
	k[0]=1; 
	for(int i=1;i<=n;i++)
		k[i]=k[i-1]*i;
	ans=k[n];
	for(int i=1;i<=m;i++)
		cin>>a[i].x>>a[i].y;
	for(int i=1;i<=m;i++)
	{
		s=0;
		memset(fx,0,sizeof(fx));
		memset(fy,0,sizeof(fy));
		dfs(1,0,i);
		if(!s) break;
		if(i&1) ans-=k[n-i]*s;
		else ans+=k[n-i]*s;
	}
	cout<<ans;
	return 0;
}
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