3059. Sculpture (jzoj)

Problem description ：

Wcyz In order to welcome the centennial celebration , Beautify the campus , Invited alumni stupid general n A sculpture , Ready to be placed on campus , The whole campus can be abstracted into a $n\times n$ Large grid of , Every $1\times 1$ At most one sculpture can be placed in the grid , But some $1\times 1$ There happens to be a canteen or lake on the grid , These grids cannot be used for placing sculptures , The shape of each sculpture is the same , In this way, the exchange arrangement in the same resettlement plan is one . Any sculpture in the same row or column is illegal .

The school wants to know how many resettlement schemes there are , Stupid wants to choose the best one , Benben wants you to tell him the number of schemes .

input:

first line , Two integers n,m（n<=20,m<=10）, Space off ,n Express nn Large grid of ,m It means that the position of the sculpture cannot be placed
The second line goes to m+1 That's ok , Two numbers per line x,y, Separate with spaces , Representation coordinates （x,y） Of 11 No sculptures can be placed on the grid .

output

a number , Number of schemes （ Number of schemes <=2^63-1）

sample input

6 7
1 1
2 1
2 2
3 3
3 4
4 3
4 4

sample output

184

hint

n<=20,m<=10

Ideas

Seeing the title, we can easily think of the number of schemes that can be filled in by pop search , But such time complexity explodes , by $O(2^n\times n)$, You can only get 10 points .

Smart little friends can definitely think of pressure DP 了 , The time complexity is $O(2^m\times m)$, Pass easily , But this konjaku doesn't press , Here is another way of thinking, inclusive .

First , Let's imagine the basic model of inclusion and exclusion in our mind , That is, three circles intersect , Calculate the area of the whole pattern .
Are we just adding the areas of three large circles first , Subtract the three middle circles , Finally, add a small circle in the middle .
We can also boldly guess the area of the whole figure , In fact, it is to add graphics that only contain an odd number of sets , Subtract figures that contain an even number of sets .

Get down to business , We can easily conclude that the total number of schemes without obstacles and problems is $(n-1)!$, Then we just need to come up with an illegal plan , Then subtract the two numbers, which is the answer .

For illegal , We consider filling in a number within the obstacle range , Write it down as $r1$, We can use search to find $r1$.
$r1$ The last row and column cannot be filled , And the rest of the $(n-1)\times (n-1)$ The grid of , No matter what plan we have , Because the front is illegal, it is illegal , The number of programmes is $r1\times (n-1)!$. Let's carry out tolerance and exclusion , Because the situation of filling in two numbers must be within the situation of filling in only one number , If we reduce more, we will $r2\times (n-2)!$ add , Finally, keep going , Find the total number of all illegal schemes , Let's preprocess factorial , Total time complexity $O(2^m)$.

The code is ugly .

code:

#include<bits/stdc++.h>
using namespace std;
long long n,m,r[31],c[31],used[3][31],x[31],y[31];
long long ans=0;
void dfs(int dep,int s,int l)
{
    
	if (s==l)
	{
    
		r[l]++;
		return ;
	}
	if (dep>m)return ;
	if (!used[1][x[dep]]&&!used[2][y[dep]])
	{
    
		used[1][x[dep]]=used[2][y[dep]]=1;
		dfs(dep+1,s+1,l);
		used[1][x[dep]]=used[2][y[dep]]=0;
	}
	dfs(dep+1,s,l);
	return ;
}
int main()
{
    
	cin>>n>>m;
	for (int i=1;i<=m;i++){
    
		cin>>x[i]>>y[i];
	}
	for (int i=1;i<=m;i++)
		dfs(1,0,i);
	c[1]=1;
	c[0]=1;
	for (int i=2;i<=n;i++)
		c[i]=c[i-1]*i;
	ans=c[n];
	for (int i=1;i<=m;i++)
	{
    
		if (i%2==1)
			ans-=c[n-i]*r[i];
		else ans+=c[n-i]*r[i];
	}
	cout<<ans;
	return 0;
}