');}

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

注意用高精！

  1. #include <cstdio>
  2. #include <cstring>
  3. #define MAXN 1000001
  4. long long max(long long a, long long b) {return a > b ? a : b;}
  5. long long tmp[MAXN] = {0, 1}, ans[MAXN], len_tmp = 1, len_ans = 0;
  6. void times(long long k) {
  7.     for (long long i = 1; i <= len_tmp; i++) tmp[i] = tmp[i] * k;
  8.     for (long long i = 1; i <= len_tmp; i++) {
  9.         if (tmp[i] >= 10) {
  10.             if (i + 1 > len_tmp) {len_tmp = i + 1;}
  11.             tmp[i + 1] += tmp[i] / 10;
  12.             tmp[i] = tmp[i] % 10;
  13.         }
  14.     }
  15. }
  16. void pow(long long k) {
  17.     for (long long i = 1; i <= k; i++) times(i);
  18. }
  19. void A(long long n, long long m) {
  20.     for (long long i = n; i >= n - m + 1; i--) { //pow(n) / pow(n - m);
  21.         times(i);
  22.     }
  23. }
  24. int main() {
  25.     long long n, m;
  26.     scanf("%lld %lld", &n, &m);
  27.     if (n + 1 >= 2 && n + 3 >= m) {
  28.         pow(n); A(n + 1, 2); A(n + 3, m);
  29.         len_ans = len_tmp;
  30.         for (long long i = 1; i <= len_tmp; i++) {
  31.             ans[i] = tmp[i];
  32.         }
  33.         memset(tmp, 0, sizeof(tmp));
  34.         tmp[1] = 1;
  35.         len_tmp = 1;
  36.     }
  37.     if (n + 2 >= m - 1 && m >= 1) {
  38.         pow(n); times(n + 1); times(2); times(m); A(n + 2, m - 1);
  39.         len_ans = max(len_ans, len_tmp);
  40.         for (long long i = 1; i <= len_ans; i++) ans[i] += tmp[i];
  41.         for (long long i = 1; i <= len_ans; i++) {
  42.             if (ans[i] >= 10) {
  43.                 if (i + 1 > len_ans) len_ans = i + 1;
  44.                 ans[i + 1] += ans[i] / 10;
  45.                 ans[i] = ans[i] % 10;
  46.             }
  47.         }
  48.     }
  49.     if (len_ans == 0) printf("0\n");
  50.     for (long long i = len_ans; i >= 1; i--) printf("%lld", ans[i]);
  51.     return 0;
  52. }