題目描述

某中學有 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)\)

然后這題要高精,就不放代碼了==

轉載于:https://www.cnblogs.com/beretty/p/10086489.html

總結

以上是生活随笔為你收集整理的[HNOI2012]排队的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。