HNOI2012排队
[HNOI2012]排队
男生不用考虑,所以可以先把男生进行排列,也就是全排列问题,答案是 。
然后再考虑老师,这就变成了一个排列组合的插空问题。老师可以分成两种情况进行考虑:
①两个老师之间有一个或更多的男生
②两个老师在一开始的时候挨在一起,后来有一个女生把他俩分开
首先先考虑①,则就是在 个空中找两个空插入 ,又因为两个老师不同,所以答案还要乘上 ,
然后再考虑女生,女生就是在 个空中找 个空插进去,所以为 。
根据乘法原理,答案就是 。
再考虑②,也就是先把两个老师捆绑起来选择,也就是 ,然后这两个老师的排列情况是 ,老师排进去的答案就是 。
女生有且仅有一个插在两个老师中间,也就是有 。
答案为 。
两种情况相加就是最终结果。
注意用高精!
#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;
}