这道题跟下面的01方阵一点关系都没有

感觉这道题把皇后换成車更好一点

---

把每一列的皇后所在位置的列数写在一行里

由题意得这便是一个 $n$ 的全排列

而还有 $n$ 个坏格子，也可以写成全排列

并且，表示皇后位置的 $n$ 个数，不能有和坏格子位置相等且数字也相等的情况

那这不就是错位排列吗？

---

有错位排列公式：

$$D_i = (i-1)*(D_{i-1}+D_{i-2})$$

注意到没有让取模，因此要用高精度

#include<iostream>
#include<cstdio>

using namespace std;

int D[210][5003],len[210];

inline void cheng(int k,int x){
	int jw=0,i=0;
	for (i=1;i<=len[k];i++){
		D[k][i]=D[k][i]*x+jw;
		jw=D[k][i]/10;
		D[k][i]%=10;
	}
	while (jw>0){
		D[k][i]=jw%10;
		jw/=10;
		i++;
	}
	len[k]=i-1;
}
inline void jia(int x){
	int k=max(len[x-1],len[x-2]);
	for (int i=1;i<=k;i++){
		D[x][i]=D[x-1][i]+D[x-2][i];
	}
	for (int i=1;i<=k;i++){
		if (D[x][i]>=10){
			D[x][i+1]+=(D[x][i]/10);
			D[x][i]%=10;
		}
	}
	if (D[x][k+1]==0) len[x]=k;
	else len[x]=k+1; 
}
inline void init(int N){
	D[2][1]=1; len[2]=1;
	for (int i=3;i<=N;i++){
		jia(i);
		cheng(i,i-1);
	}
} 

int n;

int main(){
	scanf("%d",&n);
	init(n);
	if (n==1){
		printf("0");
		return 0;
	}
	for (int i=len[n];i>=1;i--){
		printf("%d",D[n][i]);
	}
	return 0;
}

一个容斥原理做法

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

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

答案为：

$$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;
} 

通过打表可以发现

$ans[1] = 0$

$ans[i] = ans[i-1] * i + (-1)^i$

code:

#include <bits/stdc++.h>
using namespace std;

long long n;

void read() {
	cin >> n;
}

const long long N = 1010;

long long a[N], len;

void mul(long long x) {
	long long v = 0;
	for(long long i = 0; i < len; i++) {
		v = (a[i] = a[i] * x + v) / 10;
		a[i] %= 10;
	}
	while(v) {
		a[len++] = v % 10;
		v /= 10;
	}
}

void upd(int x) {
	if((x & 1) == 0) {
		long long v = 1;
		for(long long i = 0; i < len; i++) {
			v = (a[i] = a[i] + v) / 10;
			a[i] %= 10;
		}
		while(v) {
			a[len++] = v % 10;
			v /= 10;
		}
	}
	else{
		long long v = -1;
		for(long long i = 0; i < len; i++) {
			v = (a[i] = a[i] + v) / 10;
			a[i] %= 10;
		}
		while(a[len-1] == 0) len--;
	}
}

void compute() {
	len = 1;
	a[0] = 0;
	for(long long i = 2; i <= n; i++) {
		mul(i);
		upd(i);
	}
	for(long long i = len - 1; i >= 0; i--) {
		cout << a[i];
	}
}

int main() {
	read();
	compute();
	return 0;
}