题目大意
题目链接
假设一共有N对新婚夫妇,其中有M个新郎找错了新娘,求发生这种情况一共有多少种可能.
就是求 从 n中选m 个然后对m错排
分析
错排递推公式： f[i] = (i - 1) * (f[i - 1] + f[i - 2)
假设新来了一对夫妇， 其他i - 1对夫妇错排， 则新来的从i - 1中随便选一个就是(i - 1) * f[i - 1]
假设i - 2对夫妇错排， 有一对没有错排， 那么新来的必须和这个交换， 即 (i - 1) * f[i - 2]
AC代码
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| #include <bits/stdc++.h>
#define eps 1e-8
using namespace std;
#define ms(a, b) memset((a), (b), sizeof(a))
#define esp 1e-8
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int N = 5e6 + 5;
const int INF = 0x3f3f3f3f;
const ll ll_max = 4557430888798830399;
inline ll read() {
ll res = 0; bool f = 0; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = 1; ch = getchar(); }
while (ch <= '9' && ch >= '0') { res = (res << 3) + (res << 1) + ch - '0'; ch = getchar(); }
return f ? (~ res + 1) : res;
}
int t;
const int mod = 1e9 + 7;
ll c[100][100];
void get_c(int maxn){
c[0][0] = 1;
for (int i = 1; i <= maxn; ++i){
c[i][0] = 1;
for (int j = 1; j <= i; ++j){
c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
}
}
ll a, b, ans;
ll f[100];
int main(){
t = read();
get_c(20);
f[0] = 0;
f[1] = 0;
f[2] = 1;
f[3] = 2;
for (int i = 4; i <= 20; ++i)
f[i] = (i - 1) * (f[i - 1] + f[i - 2]);
while(t--){
a = read(), b= read();
cout << c[a][b] * f[b] << "\n";
}
return 0;
}
|
1
| 恰似你一低头的温柔，娇弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。
|