HNOI2012排队

Author Avatar
Actinoi 10月 21, 2020

[HNOI2012]排队

男生不用考虑，所以可以先把男生进行排列，也就是全排列问题，答案是 n! 。

然后再考虑老师，这就变成了一个排列组合的插空问题。老师可以分成两种情况进行考虑：

①两个老师之间有一个或更多的男生
②两个老师在一开始的时候挨在一起，后来有一个女生把他俩分开

首先先考虑①，则就是在 n+1 个空中找两个空插入 C_{n+1}^{2} ，又因为两个老师不同，所以答案还要乘上 2! ， C_{n+1}^{2}\times 2! = A_{n+1}^{2}

然后再考虑女生，女生就是在 n + 3 个空中找 m 个空插进去，所以为 A_{n+3}^m 。

根据乘法原理，答案就是 n! \times A_{n+1}^{2} \times A_{n+3}^m 。

Xnip2020-10-21_17-22-02.jpg

再考虑②，也就是先把两个老师捆绑起来选择，也就是 C_{n+1}^1=n+1 ，然后这两个老师的排列情况是 2! ，老师排进去的答案就是 (n+1) \times 2 。

女生有且仅有一个插在两个老师中间，也就是有 m\times A_{n+2}^{m-1} 。

答案为 n! \times (n+1) \times 2 \times m\times A_{n+2}^{m-1} 。

两种情况相加就是最终结果。

Xnip2020-10-21_17-30-02.jpg

注意用高精！

#include <cstdio>
#include <cstring>
#define MAXN 1000001
long long max(long long a, long long b) {return a > b ? a : b;}
long long tmp[MAXN] = {0, 1}, ans[MAXN], len_tmp = 1, len_ans = 0;
void times(long long k) {
    for (long long i = 1; i <= len_tmp; i++) tmp[i] = tmp[i] * k;
    for (long long i = 1; i <= len_tmp; i++) {
        if (tmp[i] >= 10) {
            if (i + 1 > len_tmp) {len_tmp = i + 1;}
            tmp[i + 1] += tmp[i] / 10;
            tmp[i] = tmp[i] % 10;
        }
    }
}
void pow(long long k) {
    for (long long i = 1; i <= k; i++) times(i);
}
void A(long long n, long long m) {
    for (long long i = n; i >= n - m + 1; i--) { //pow(n) / pow(n - m);
        times(i);
    }
}
int main() {
    long long n, m;
    scanf("%lld %lld", &n, &m);
    if (n + 1 >= 2 && n + 3 >= m) {
        pow(n); A(n + 1, 2); A(n + 3, m);
        len_ans = len_tmp;
        for (long long i = 1; i <= len_tmp; i++) {
            ans[i] = tmp[i];
        }
        memset(tmp, 0, sizeof(tmp));
        tmp[1] = 1;
        len_tmp = 1;
    }
    if (n + 2 >= m - 1 && m >= 1) {
        pow(n); times(n + 1); times(2); times(m); A(n + 2, m - 1);
        len_ans = max(len_ans, len_tmp);
        for (long long i = 1; i <= len_ans; i++) ans[i] += tmp[i];
        for (long long i = 1; i <= len_ans; i++) {
            if (ans[i] >= 10) {
                if (i + 1 > len_ans) len_ans = i + 1;
                ans[i + 1] += ans[i] / 10;
                ans[i] = ans[i] % 10;
            }
        }
    }
    if (len_ans == 0) printf("0\n");
    for (long long i = len_ans; i >= 1; i--) printf("%lld", ans[i]);
    return 0;
}