首页 > 其他 > 详细

[HNOI2012]排队

时间:2018-12-08 10:41:33      阅读:138      评论:0      收藏:0      [点我收藏+]

题目描述

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

输入输出格式

输入格式:

只有一行且为用空格隔开的两个非负整数 n 和 m,其含义如上所述。 对于 30%的数据 n<=100,m<=100 对于 100%的数据 n<=2000,m<=2000

输出格式:

输出文件 output.txt 仅包含一个非负整数,表示不同的排法个数。注意答案可能很大。

输入输出样例

输入样例#1: 复制

1 1

输出样例#1: 复制

12


排列组合

首先考虑插板

先排上n个男生,方案数为\(A(n,n)\)

这样就形成了\(n+1\)个空位,所以我们再把老师放进这\(n+1\)个空位中,方案数为\(A(n + 1,2)\)

然后再把剩下的\(m\)个女生放进现在形成的\(n+3\)个空位中,方案数为\(A(n+3,m)\)

这时答案就是\(A(n,n)*A(n+1,2)*A(n+3,m)\)

这样答案就算小了

因为我们这样只考虑了用男生把老师给分开

没有考虑用女生把老师个分开

所以我们还应该考虑用两个老师中间夹着一个女生的情况

就考虑把任意一个女生跟两个老师捆在一块当成一个往里面放

所以这时答案就是\(A(n,n) * (n + 1) * 2 ‘* m * A(n + 2 , m - 1)\)

最后总答案就是\(Ans = A(n,n) * A(n+1,2) * A(n+3,m) + A(n,n) * (n+1) * 2 * m * A(n + 2 , m - 1)\)

然后这题要高精,就不放代码了==

[HNOI2012]排队

原文:https://www.cnblogs.com/beretty/p/10086489.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!