[HNOI 2012] 排队

题目大意

nn 名男同学,mm 名女同学和两名老师要排队参加体检。他们排成一条直线,并且任意两名女同学不能相邻,两名老师也不能相邻,求一共有多少种排法(注意:任意两个人都是不同的)。

1n,  m2,0001 \leqslant n, \; m \leqslant 2,000

题目链接

【HNOI 2012】排队 - Luogu 3223

题解

纯数学题 + 高精度,就做一个高精度的版子吧。。。

考虑先让老师站一起和男生排队,有 2(n+1)!2(n + 1)! 种,再选一个女生插到老师之间,剩下的 m1m - 1 个女生插入到 n+2n + 2 个空之间(两个老师与之间的女生可视作一个男生),答案为 2m(n+1)!(n+2)m12m(n + 1)!(n + 2)^{\underline{m - 1}}

再考虑老师由男生插开,即在排好的男生中的 n+1n + 1 个空中插两个,再在这 n+3n + 3 个空中插入女生,答案为 n!(n+1)2(n+3)mn!(n + 1)^{\underline{2}}(n + 3)^{\underline{m}}

最终答案为:

n!(  2m(n+1)(n+2)m1+(n+1)2(n+3)m  )n! ( \; 2m(n + 1)(n + 2)^{\underline{m - 1}} + (n + 1)^{\underline{2}}(n + 3)^{\underline{m}} \; )

代码

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <cstdio>
#include <cstring>
#include <algorithm>
const int MAXN = 2005;
struct BigInteger {
int len, a[20000];
BigInteger(int num = 0) {
memset(a, 0, sizeof (a));
len = 1;
while (num) {
a[len++] = num % 10;
num /= 10;
}
maintain();
}
void print() const {
for (int i = len; i; i--) printf("%d", a[i]);
puts("");
}
void maintain() {
while (a[len + 1]) len++;
while (!a[len] && len > 1) len--;
}
static int getLength(int x) {
int len = 0;
while (x) {
x /= 10;
len++;
}
if (len == 0) len = 1;
return len;
}
BigInteger operator+(const BigInteger &another) const {
BigInteger res;
res.len = std::max(len, another.len);
for (int i = 1; i <= res.len; i++) {
res.a[i] += a[i] + another.a[i];
if (res.a[i] > 10) {
res.a[i] -= 10;
res.a[i + 1]++;
}
}
res.maintain();
return res;
}
BigInteger operator*(int another) const {
BigInteger res;
res.len = len + getLength(another);
for (int i = 1; i <= res.len; i++) {
res.a[i] += a[i] * another;
res.a[i + 1] += res.a[i] / 10;
res.a[i] %= 10;
}
res.maintain();
return res;
}
};
void mulPermu(BigInteger &a, int n, int m) {
if (n < m) a = a * 0;
else for (int i = n; i > n - m; i--) a = a * i;
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
BigInteger a(2), b(1);
mulPermu(a, n + 2, m - 1);
a = a * m;
a = a * (n + 1);
mulPermu(b, n + 1, 2);
mulPermu(b, n + 3, m);
a = a + b;
mulPermu(a, n, n);
a.print();
return 0;
}