HNOI2012排队题解

发表于 | 更新于 | 分类于 ， ， ，

排队,打水?

题目描述

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

题目简述：

n个男生,m个女生,2个老师,排成一个队列,老师不能相邻,女生不能相邻,每个人不同

算法分析

这里有一个神奇的群体叫男生,就像背景一样,没有任何要求

所以?这题实际上就是疯狂把老师和女生丢到男生之间的空里面,由于只有两个老师,我们只用分两种情况:

  • 两个老师之间只有一个女生
  • 两个老师之间有一坨不明觉厉的东西

那么既然是插空,那么就是排列组合乱搞咯.

算法实现

  • 况一

我们既然这个状态如此死板,那我们就直接把它当做一个整体吧!

男生排列:$A_n^n$

上述总体排列:$A_{n+1}^1$(n+1是因为有n+1个空)

总体中老师排列:$A_2^2$

剩余女生排列:$A_{n+2}^{m-1}$

乘起来就完咯

  • 况二

剩下直接考虑:

男生排列:$A_n^n$

老师排列:$A_{n+1}^2$

女生排列:$A_{n+3}^{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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<bitset>
#include<vector>
#include<set>
#include<map>
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long db
#define si short int
#define bl bool
#define mem(a) memset(a,0,sizeof(a))
#define mee(a,b) memset(a,b,sizeof(a))
#define setnum(a,b,c) for(int kkk=1;i<=b;i++)a[kkk]=c[kkk];
#define setnums(a,b,c) for(int kkk=1;kkk<=b;kkk++)a[kkk]=c;
#define maxn 20015
#define maxm
#define inf 0x7fffffff
#define r(a) a=read()
#define w(a) write(a);puts("")
#define W(a) write(a);printf(" ")
#define For(a,b,c) for(int a=b;a<=c;a++)
using namespace std;
ll Min(ll x,ll y){if(x<y)return x;return y;}
ll Max(ll x,ll y){if(x>y)return x;return y;}
ll read(){
	ll s=0,h=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')h=-1;c=getchar();}
	while(c>='0'&&c<='9'){s=s*10+c-'0';c=getchar();}
	return s*h;
}
void write(ll x){
	if(x>9){
		si tmp=x%10;
		write(x/10);
		putchar(tmp+'0');
	}
	else putchar(x+'0');
}
ll Pow(ll x,ll y,ll p){
	ll ans=1;
	while(y){
		if(y&1)ans=ans*x%p;
		x=x*x%p;y>>=1;
	}
	return ans;
}
ll v[maxn],c[maxn];
ll n,m;
void times(ll a[],ll val)
{
	for(register ll i=1;i<=a[0];i++)a[i]*=val;
	for(register ll i=1;i<=a[0];i++)
	{
		a[i+1]+=a[i]/10;a[i]%=10;
	}
	while(a[a[0]+1]){a[0]++;a[a[0]+1]+=a[a[0]]/10;a[a[0]]%=10;}
}
void add(ll a[],ll b[])
{
	a[0]=max(a[0],b[0])+1;
	for(register ll i=1;i<=a[0];i++)
	{
		a[i]+=b[i];
	}
	for(register ll i=1;i<=a[0];i++)
	{
		a[i+1]+=a[i]/10;a[i]%=10;
	}
	if(!a[a[0]])a[0]--;
}
void print(ll a[])
{
	for(register ll i=a[0];i>=1;i--)printf("%lld",a[i]);
	printf("\n");
}
int main(){
	n=read();
	m=read();
	v[0]=v[1]=c[0]=c[1]=1;
	times(v,n);
	for(register ll i=1;i<=n+1;i++)times(v,i);
	for(register ll i=n+4-m;i<=n+3;i++)times(v,i);
	if(m){
		for(register ll i=1;i<=n+1;i++)times(c,i);
		for(register ll i=n-m+4;i<=n+2;i++)times(c,i);
		times(c,2);
		times(c,m);
		add(v,c);
	}
	print(v);
	return 0;
}

Tips

数据很大，又不取模，你猜要不要高精度？