洛谷 P3182 [HAOI2016]放棋子（错排问题）

题面

luogu

题解

裸的错排问题

错排问题

百度百科：\(n\)个有序的元素应有\(n!\)个不同的排列，如若一个排列使得所有的元素不在原来的位置上，则称这个排列为错排；有的叫重排。如，1 2的错排是唯一的，即2 1。1 2 3的错排有3 1 2，2 3 1。这二者可以看作是1 2错排，3分别与1、2换位而得的。

错排公式：\(D(n) = (n-1)*(D(n-1)+D(n-2))\)

这里给出解释：

对于错排可以看作连线

A B ...... C

a b ...... c

\(A\)不能连\(a\)，

同理，\(B\)不能连\(b\)，\(C\)不能连\(c\)

考虑\(c\)连线

有\((n-1)\)种方案

假设\(A-c\)

那么考虑\(a\)如何连

1.如果\(C-a\)那么剩下的又是一个错排，即\(D(n-2)\)

2.如果\(a\)不连\(C\)， 那么也可以构成一个错排，即\(D(n-1)\)

问题转换

如何转换成错排问题呢？

因为每行每列都只有一个棋子，且不能放在障碍上。

那么可以看作对障碍的错排

然后就是高精度板子了

Code

#include<bits/stdc++.h>

#define LL long long

#define RG register

using namespace std;

template<class T> inline void read(T &x) {

	x = 0; RG char c = getchar(); bool f = 0;

	while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') c = getchar(), f = 1;

	while (c >= '0' && c <= '9') x = x*10+c-48, c = getchar();

	x = f ? -x : x;

	return ;

}

template<class T> inline void write(T x) {

	if (!x) {putchar(48);return ;}

	if (x < 0) x = -x, putchar('-');

	int len = -1, z[20]; while (x > 0) z[++len] = x%10, x /= 10;

	for (RG int i = len; i >= 0; i--) putchar(z[i]+48);return ;

}

const int N = 10005;

struct node {

	int s[N], cnt;

	node(){

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

	}

	node operator + (node z) const {

		node tmp;

		tmp.cnt = max(cnt, z.cnt);

		for (int i = 0; i < tmp.cnt; i++)

			tmp.s[i] = s[i]+z.s[i];

		for (int i = 0; i < tmp.cnt; i++)

			if (tmp.s[i] > 9) {

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

				if (i+1 == tmp.cnt) tmp.cnt++;

				tmp.s[i] %= 10;

			}

		return tmp;

	}

	node operator * (int z) const {

		node tmp;

		tmp.cnt = cnt;

		for (int i = 0; i < tmp.cnt; i++)

			tmp.s[i] = s[i]*z;

		for (int i = 0; i < tmp.cnt; i++)

			if (tmp.s[i] > 9) {

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

				if (i+1 == tmp.cnt) tmp.cnt++;

				tmp.s[i] %= 10;

			}

		return tmp;

	}

};

node D[210];

int main() {

	int n;

	read(n);

	D[2].s[0] = D[2].cnt = D[1].cnt = 1;

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

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

	for (int i = D[n].cnt-1; i >= 0; i--)

		printf("%d", D[n].s[i]);

	return 0;

}