一个容斥原理做法

首先我们发现坏格子也是一种合法的皇后排列方式。

然后我们枚举某些皇后的排列方式中占用了多少个坏格子，剩下的部分全排列，然后容斥。

答案为：

$$n!-\sum\limits_{i=1}^n {n \choose i}(n-i)!(-1)^{i} $$

化简一下就是：

$$\sum\limits_{i=2}^n \frac{n!}{i!}(-1)^i$$

然后高精度直接做。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[501000],nw[501000],nlen;
const int L=1e8;
void MulNow(int x){
	for(int i=1;i<=nlen;i++){
		nw[i]=nw[i]*x;
		
	}for(int i=1;i<=nlen;i++){
		if(nw[i]>=L){
			nw[i+1]=nw[i+1]+nw[i]/L;
			nw[i]%=L;
			nlen=max(nlen,i+1);
		}
	}
}void PlsNow(int f){
	for(int i=1;i<=nlen;i++){
		a[i]=a[i]+nw[i]*f;
	}
}
signed main(){
//	freopen("ex.in","r",stdin);
//	freopen("my.out","w",stdout);
//	system("fc my.out ex.out");return 0;
	cin>>n;
	for(int i=1;i<=n*n;i++) cin>>nlen;
	nw[nlen=1]=1;
	for(int i=n;i>=2;i--){
		if(i%2==1){
			PlsNow(-1);
		}else PlsNow(1);
		MulNow(i);
	}
	for(int i=1;i<=nlen;i++){
		if(a[i]<0){
			int pls=(L-1-a[i])/L;
			a[i+1]=a[i+1]-pls;
			a[i]=a[i]+pls*L;
		}if(a[i]>=L){
			a[i+1]=a[i+1]+a[i]/L;
			a[i]%=L;
			nlen=max(nlen,i+1);
		}
	}
	for(int i=nlen;i>=1;i--){
		if(i!=nlen){
			if(a[i]<1e7) cout<<0;
			if(a[i]<1e6) cout<<0;
			if(a[i]<1e5) cout<<0;
			if(a[i]<1e4) cout<<0;
			if(a[i]<1e3) cout<<0;
			if(a[i]<1e2) cout<<0;
			if(a[i]<1e1) cout<<0;
		}cout<<a[i];
	}
	return 0;
}