「LGOJ」信封问题/错排/放棋子

题意

某人写了n封信和n个信封,如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况

link

题解

​ 我们记$D(i)$为当有i个信封的总共情况数量

​ 特别的:
$$
D_{1}=0,D_{2}=1,D_{3}=2
$$
​ 现在多了一个信封,那么为了错开,这个信$n$,除了他本身第$n$个信封不能放

​ 其他都可以放,那么有$n-1$个位置可以放.那么剩下就有$D_{i-1}$种可能,所以

$$
D_{i}=(i-1)\times D_{i-1}
$$

​ 巴特!还没完!对于一个信k,我们可以分为两种情况

  • K放进了n号信封

  • K没有放进n号信封

      对于K放进了n号信封时,不难发现还有$D_{i-1}$种情况
    

$$
把 n 号球放进:
1号箱子 \longrightarrow D_{n-2}+D_{n-1}\
\\
2号箱子 \longrightarrow D_{n-2}+D_{n-1}D \
(k-1)号箱子 \longrightarrow D_{n-2}+D_{n-1}\
\text{k}号箱子 \longrightarrow D_{n-2}+D_{n-1}\
$$

​ 得到递推式子
$$
D_{i}=(D_{i-1}+D_{i-2}) \times (i-1)
$$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>

#define ll long long
#define RE register

ll n,f[30];

inline void fread(ll &x) {
x = 0;
int f = 1;
char ch = getchar();
while(ch < '0'||ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0'&&ch <= '9') {
x = (x<<3) + (x<<1) + (ch^48);
ch = getchar();
}
x = x * f;
}


int main() {
f[1] = 0;
f[2] = 1;
f[3] = 2;
fread(n);
for(RE int i = 4; i <= n;i++)
f[i] = (f[i-1] + f[i-2]) * (i-1);
std::printf("%lld",f[n]);
return 0;
}
0%