错排问题
n个有序的元素应有n!个不同的排列，如若一个排列使得所有的元素不在原来的位置上，则称这个排列为错排；有的叫重排。——百度百科
嗯，这就是错排
例题引入
例题1
LGOJ P1595 信封问题
我们读完题后，发现这是一道相当裸的错排题
我们考虑使用递推的方法求解。
设
D
[
n
]
D[n]
D
[
n
]
表示将
n
n
n
个元素错排后可得到的方案数
我们一般分以下几步考虑如何求
D
[
n
]
D[n]
D
[
n
]
：
1、将第
n
n
n
号元素放到前
n
−
1
n-1
n
−
1
个位置上去（设这个位置原来的元素是
k
k
k
），方案数是
n
−
1
n-1
n
−
1
.
2、考虑第
k
k
k
个元素怎么办
（1）若第
k
k
k
个元素放到第
n
n
n
个位置上去，其余
n
−
2
n-2
n
−
2
个元素可以随意错排，方案数为
D
[
n
−
2
]
D[n-2]
D
[
n
−
2
]
（2）若第
k
k
k
个元素不放到第
n
n
n
个位置上去，则包括
k
k
k
在内的
n
−
1
n-1
n
−
1
个元素可以随意错排，方案数为
D
[
n
−
1
]
D[n-1]
D
[
n
−
1
]
综合（1）（2），由加法原理可得，第2、种情况的总方案数为
D
[
n
−
2
]
+
D
[
n
−
1
]
D[n-2]+D[n-1]
D
[
n
−
2
]
+
D
[
n
−
1
]
再综合1、2、，由乘法原理可得，
D
[
n
]
=
(
n
−
1
)
(
D
[
n
−
2
]
+
D
[
n
−
1
]
)
D[n]=(n-1)(D[n-2]+D[n-1])
D
[
n
]
=
(
n
−
1
)
(
D
[
n
−
2
]
+
D
[
n
−
1
]
)
这就是错排数的计算公式！
好的，推了这么多，这道题总算能A了
代码
#define USEFASTERREAD 1
#define rg register
#define inl inline
#define DEBUG printf("[Passing [%s] in line %d.]\n", __func__, __LINE__)
#define putline putchar('\n')
#define putsp putchar(' ')
#define Rep(a, s, t) for(rg int a = s; a <= t; a++)
#define Repdown(a, t, s) for(rg int a = t; a >= s; a--)
typedef long long ll;
#include<cstdio>
#if USEFASTERREAD
char In[1 << 20], *ss = In, *tt = In;
#define getchar() (ss == tt && (tt = (ss = In) + fread(In, 1, 1 << 20, stdin), ss == tt) ? EOF : *ss++)
#endif
struct IO {
void RS() {freopen("test.in", "r", stdin), freopen("test.out", "w", stdout);}
template<typename T> inline IO r(T& x)const {
x = 0; T f = 1; char ch = getchar();
for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + int(ch - '0');
x *= f; return *this;
}
template<typename T> inline IO w(T x)const {
if(x < 0) {putchar('-'); x = -x;}
if(x >= 10) w(x / 10);
putchar(x % 10 + '0'); return *this;
}
template<typename T> inline IO wl(const T& x)const {w(x), putline; return *this;}
template<typename T> inline IO ws(const T& x)const {w(x), putsp; return *this;}
inline IO l() {putline; return *this;}
inline IO s() {putline; return *this;}
}io;
template<typename T> inline T Max(const T& x, const T& y) {return y < x ? x : y;}
template<typename T> inline T Min(const T& x, const T& y) {return y < x ? y : x;}
template<typename T> inline void Swap(T& x, T& y) {T tmp = x; x = y; y = tmp;}
template<typename T> inline T Abs(const T& x) {return x > 0 ? x : -x;}
int n;
ll f[25];
int main() {
//io.RS();
io.r(n);
f[1] = 0; f[2] = 1;
for(rg int i = 3; i <= n; i++)
f[i] = (i - 1) * (f[i - 2] + f[i - 1]);
io.wl(f[n]);
return 0;
}
例题2
P3182 [HAOI2016]放棋子
这是道很垃圾的省选题
好的。这题本质上还是一道错排裸题。
我们看看输入的矩阵
[
0
1
1
0
]
\begin{bmatrix} 0&1\\1&0\end{bmatrix}
[
0
1
1
0
]
既然我们要求的是方案数，这玩意和
[
1
0
0
1
]
\begin{bmatrix} 1&0\\0&1\end{bmatrix}
[
1
0
0
1
]
是等价的。
我们可以这样说：第一行的元素不能放第一格，第二行的元素不能放第二格…并且元素不能在同一列。
这不就是裸的
错排
吗！
ok，和我一起背公式：
D
[
n
]
=
(
n
−
1
)
(
D
[
n
−
2
]
+
D
[
n
−
1
]
)
D[n]=(n-1)(D[n-2]+D[n-1])
D
[
n
]
=
(
n
−
1
)
(
D
[
n
−
2
]
+
D
[
n
−
1
]
)
好的，我们把第一道例题的照搬过去就好了嘛。
才怪
这道题毕竟是道省选题。还要打个高精。
代码
#define USEFASTERREAD 1
#define rg register
#define inl inline
#define DEBUG printf("[Passing [%s] in line %d.]\n", __func__, __LINE__)
#define putline putchar('\n')
#define putsp putchar(' ')
#define Rep(a, s, t) for(rg int a = s; a <= t; a++)
#define Repdown(a, t, s) for(rg int a = t; a >= s; a--)
typedef long long ll;
#include<cstdio>
#if USEFASTERREAD
char In[1 << 20], *ss = In, *tt = In;
#define getchar() (ss == tt && (tt = (ss = In) + fread(In, 1, 1 << 20, stdin), ss == tt) ? EOF : *ss++)
#endif
struct IO {
void RS() {freopen("test.in", "r", stdin), freopen("test.out", "w", stdout);}
template<typename T> inline IO r(T& x)const {
x = 0; T f = 1; char ch = getchar();
for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + int(ch - '0');
x *= f; return *this;
}
template<typename T> inline IO w(T x)const {
if(x < 0) {putchar('-'); x = -x;}
if(x >= 10) w(x / 10);
putchar(x % 10 + '0'); return *this;
}
template<typename T> inline IO wl(const T& x)const {w(x), putline; return *this;}
template<typename T> inline IO ws(const T& x)const {w(x), putsp; return *this;}
inline IO l() {putline; return *this;}
inline IO s() {putline; return *this;}
}io;
template<typename T> inline T Max(const T& x, const T& y) {return y < x ? x : y;}
template<typename T> inline T Min(const T& x, const T& y) {return y < x ? y : x;}
template<typename T> inline void Swap(T& x, T& y) {T tmp = x; x = y; y = tmp;}
template<typename T> inline T Abs(const T& x) {return x > 0 ? x : -x;}
//D[n] = (n - 1) * (D[n - 1] + D[n - 2])
#include<cstring>
const int NN = 100000000, N = 8;
const int MAXLEN = 1005;
struct Bigint {
ll A[MAXLEN / N + 1];
int len;
Bigint(ll x = 0) {
memset(A, 0x00, sizeof A);
if(x == 0) len = 1;
else {
len = 0;
while(x) {
A[len++] = x % NN;
x /= NN;
}
}
}
void Write() {
io.w(A[len - 1]);
for(rg int i = len - 2; i >= 0; i--) {
for(rg int j = NN / 10; A[i] < j; j /= 10) putchar('0');
if(A[i]) io.w(A[i]);
}
}
ll& operator[] (const int& k) {return A[k];}
ll operator[] (const int& k)const {return A[k];}
Bigint operator + (const Bigint& B)const {
Bigint C;
C.len = Max(len, B.len);
for(rg int i = 0; i < C.len; i++) {
C[i] += A[i] + B[i];
C[i + 1] += C[i] / NN;
C[i] %= NN;
}
if(C[C.len]) C.len++;
while(C[C.len - 1] == 0 && C.len > 1) C.len--;
return C;
}
Bigint operator * (const int& B)const {
Bigint C;
C.len = len;
for(rg int i = 0; i < C.len; i++) {
C[i] += A[i] * B;
C[i + 1] += C[i] / NN;
C[i] %= NN;
}
if(C[C.len]) C.len++;
while(C[C.len - 1] == 0 && C.len > 1) C.len--;
return C;
}
};
int n;
Bigint D[205];
int main() {
//io.RS();
io.r(n);
D[1] = 0;
D[2] = 1;
for(rg int i = 3; i <= n; i++) {
D[i] = (D[i - 2] + D[i - 1]) * (i - 1);
}
D[n].Write();
return 0;
}