[HNOI 2012] 排队

发表于2017-04-23更新于2020-08-06

题目大意

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

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

题目链接

【HNOI 2012】排队 - Luogu 3223

题解

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

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

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

最终答案为：

n!(  2m(n+1)(n+2)m−1‾+(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;
}