题目链接

戳这

前置知识

• 错位排序

Solution

我们可以观察发现，每一行的障碍位置对答案并没有影响。

于是我们可以将此时的矩阵化成如下形式:

此时障碍列的排列为:

1 2 3 4

于是我们问题可以转化为：

从每行中选出一个\(1\)~\(n\)的没出现的书且和障碍不相同

即：问一个\(1\)~\(n\)的数列的排列与原数列的位置都不相同的个数

所以这就是一个错位排序了，但是为了让代码量变大，便没有模数，所以要打高进度

Code

我不会告诉你我的高进度是copy的模板的

#include<bits/stdc++.h>

using namespace std;

const int MAXN=5005;

struct bign {

	int len, s[MAXN];

	bign () {

		memset(s, 0, sizeof(s));

		len = 1;

	}

	bign (int num) {

		*this = num;

	}

	bign (const char *num) {

		*this = num;

	}

	bign operator = (const int num) {

		char s[MAXN];

		sprintf(s, "%d", num);

		*this = s;

		return *this;

	}

	bign operator = (const char *num) {

		for(int i = 0; num[i] == '0'; num++) ;

		len = strlen(num);

		for(int i = 0; i < len; i++) s[i] = num[len-i-1] - '0';

		return *this;

	}

	bign operator + (const bign &b) const {

		bign c;

		c.len = 0;

		for(int i = 0, g = 0; g || i < max(len, b.len); i++) {

			int x = g;

			if(i < len) x += s[i];

			if(i < b.len) x += b.s[i];

			c.s[c.len++] = x % 10;

			g = x / 10;

		}

		return c;

	}

	void clean() {

		while(len > 1 && !s[len-1]) len--;

	}

	bign operator * (const bign &b) {

		bign c;

		c.len = len + b.len;

		for(int i = 0; i < len; i++) {

			for(int j = 0; j < b.len; j++) {

				c.s[i+j] += s[i] * b.s[j];

			}

		}

		for(int i = 0; i < c.len; i++) {

			c.s[i+1] += c.s[i]/10;

			c.s[i] %= 10;

		}

		c.clean();

		return c;

	}

	string str() const {

		string res = "";

		for(int i = 0; i < len; i++) res = char(s[i]+'0')+res;

		return res;

	}

};

ostream& operator << (ostream &out, const bign &x) {

	out << x.str();

	return out;

}

bign d[2001];

int main() {

	int  n;

	cin>>n;

	d[2]=1;

	for(int i=3; i<=n; i++)

		d[i]=(d[i-1]+d[i-2])*(i-1);

	cout<<d[n];

	return 0;

}