Description

某中學有 n 名男同學，m 名女同學和兩名老師要排隊參加體檢。他們排成一條直線，并且任意兩名女同學不能相鄰，兩名老師也不能相鄰，那么一共有多少種排法呢？（注意：任意兩個人都是不同的） ?

Input

只有一行且為用空格隔開的兩個非負整數 n 和 m，其含義如上所述。 ? 對于 30%的數據 n≤100,m≤100 ? 對于 100%的數據 n≤2000,m≤2000

Output

輸出文件 output.txt 僅包含一個非負整數，表示不同的排法個數。注意答案可能很大。

Sample Input

1 1

Sample Output

12

碼題5分鐘，推導兩小時

對于“不能相鄰”，考慮采用插空法

首先對于無限制的男生有$A_n^n$種排列

這時產生了n+1個空檔，插入2個老師還要$*A_{n+1}^2$

現在有n+3個空檔，放m個女生有$A_{n+3}^m$種

此時的所有情況都滿足條件

但只考慮了男生隔開老師的情況

而女生也可以隔開老師

考慮捆綁play（霧）法

讓兩個老師一個女生卡在一起（盧老爺我錯遼）

這種組合放入男生隊伍中有$n+1$種位置

選著一個女生有m種

放剩下的$A_{n+2}^{m-1}$

老師排列方式$A_2^2=2$

男生排列方式$A_n^n$

$ANS=A_n^n*A_{n+1}^2*A_{n+3}^m+(n+1)*2*A_n^n*m*A_{n+2}^{m-1}$

?

連高精乘低精都不會打了真是恥辱

#include<cstdio> #include<iostream> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int N=100005; int n,m,num1[N],num2[N],tot[N]; /*int intlen(int x) {return (int)log10(x)+1; } void turn(int x,int num[]) {int l=0;while(x){int now=x%10;num[++l]=now;x/=10;}num[0]=l;//reverse(num+1,num+l+1); }*/ void mult(int x,int num[]) {int k=0;for(int i=1;i<=num[0];i++){int tmp=num[i]*x+k;num[i]=tmp%10;k=tmp/10;}while(k)num[++num[0]]=k%10,k/=10; } void sum(int a1[],int a2[],int res[]) {int j=1,x=0;while(j<=a1[0]||j<=a2[0]){res[j]=a1[j]+a2[j]+x;x=res[j]/10;res[j]%=10;j++;}res[j]=x;if(!res[j])j--;res[0]=j; } void print(int a[]) {for(int i=a[0];i;i--)printf("%d",a[i]);puts(" "); } int main() {scanf("%d%d",&n,&m);//turn(n,num1);turn(m,num2);num1[0]=num1[1]=1;for(int i=1;i<=n;i++)mult(i,num1);for(int i=n+1;i>=n;i--)mult(i,num1);for(int i=n+3;i>=n-m+4;i--)mult(i,num1);num2[0]=num2[1]=1;mult(n+1,num2);mult(m,num2);mult(2,num2);for(int i=n+2;i>=n+2-(m-1)+1;i--)mult(i,num2);for(int i=1;i<=n;i++)mult(i,num2);//print(num1);print(num2); sum(num1,num2,tot);print(tot);return 0; } View Code

?

轉載于:https://www.cnblogs.com/Rorschach-XR/p/11101993.html

總結

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

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