HNOI 排队

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

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

样例输入

1 1

样例输出

12

码量很小,关键是式子和高精。

插空和捆绑思想,加法定理。

先插入两个老师,因为老师只有两个,而男生就算只有一个也可以隔开,但先插入女生的话可能有未隔开但需要老师隔开的情况。

考虑老师有两种情况

(一开始我只考虑了一种,且先插入的是女生,然后样例过了,一直认为自己的式子是对的认为高精上出了错...不要轻信样例

   然后发现要先插入老师,该成这个后样例就过不了了,开始水样例手摸,终于发现少了一种情况...)。

A(n,n)*A(n+1,2)*A(n+3,m)+A(n,n)*A(n+1,1)*A(2,2)×A(m,1)×A(n+2,m-1)

第一种:A(n,n)*A(n+1,2)*A(n+3,m);不让两个老师挨着插入,然后插空法插入女生;

第二种(易忽略):两个老师一开始可以挨着啊,然后用女生来隔开(没有手摸感觉我是找不出来了...)

所以让一个女生和两个老师绑在一起插空。但这里需要注意女生有m个所以有m种,老师之间也有两种排法;

A(n,n)*A(n+1,1)*2*m*A(n+2,m-1)(剩下的女生插空);

或者写成A(n,n)*A(n+1,1)*A(2,2)[两个老师间]×A(m,1)[写成C(m,1)也行,m个里选出一个](三捆绑插空及内部)×A(n+2,m-1);

高精上:只用高精乘低精和高精加就行,把A除的式子直接消去分母,注意不要用高精乘高精,同一个大式子里用一个数组一直高精乘低精,会快很多。

 

总结:

1.不要迷信样例和自己的式子;

2.手动模拟的好处;

3.每一个点和式子,每一种情况都要考虑到位(分情况);

4.简化消去式子,高精变低精。

5.能优化的地方一定要优化。

上一篇:HNOI 2009 有趣的数列


下一篇:【[HNOI/AHOI2018]毒瘤】