题目描述
某中学有 n 名男同学，m 名女同学和两名老师要排队参加体检。他们排成一条直线，并且任意两名女同学不能相邻，两名老师也不能相邻，那么一共有多少种排法呢？（注意：任意两个人都是不同的）
输入格式
只有一行且为用空格隔开的两个非负整数 n 和 m，其含义如上所述。
对于 30%的数据 n≤100,m≤100
对于 100%的数据 n≤2000,m≤2000
输出格式
输出文件 output.txt 仅包含一个非负整数，表示不同的排法个数。注意答案可能很大。
样例
样例输入
1 1样例输出
12正经高精组合数学题。
任意两个人都不同，所以要求排列。A(n,m)=n!/(n-m)!
来推一波柿子：
先将男生全排列，再将2个老师插进n+1个空里。A(n,n)*A(n+1,2)
再将女生插入此时的n+3个空中，A(n+3,m)
以上A(n,n)*A(n+1,2)*A(n+3,m)好像没什么问题，然后你手模下样例会发现事情并不是那么简单
其实以上并没有考虑到老师只由女生隔开的情况
既然如此就先将TGT的形态捆绑，对于捆绑中的G有A(m,1)，T有A(2,2)，则捆绑整体A(m,1)*A(2,2)
因为捆绑只有一个，所以可以将其视为男生并全排列，A(n+1,n+1)
接下来还剩下m-1个女生，插入目前的n+2个空中。A(n+2,m-1)
A(m,1)*A(2,2)*A(n+1,n+1)*A(n+2,m-1)
以上两个事件互斥，加法原理即可
即 A(n,n)*A(n+1,2)*A(n+3,m)+A(m,1)*A(2,2)*A(n+1,n+1)*A(n+2,m-1)
然后就是高精，不要用A(n,m)=n!/(n-m)!，高精除恶心死。
化简下柿子： n*(n+1)*n!*(n+3)!/(n-m+3)!+2*m*(n+1)!*(n+2)!/(n-m+3)!
对于(n+3)!/(n-m+3)!之类只要求从(n-m+4)到(n+3)的累乘
来个百亿进制低精乘高精，每次乘高精数最多增加一位，所以只用多加一位。
PS小技巧：printf(“%0xd”,a); 可以对a不足x位的部分补零。
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<cstring> 5 #define ll long long 6 #define base 10000000000 7 #define reg register 8 #define F(i,a,b) for(i=a;i<=b;++i) 9 using namespace std; 10 ll c[100005],a[100005],b[100005]; 11 void dcheng(ll a[],int n) 12 { 13 reg int i; reg ll x=0; a[0]=a[0]+1; 14 F(i,1,a[0]) 15 { 16 a[i]=a[i]*n+x; 17 x=a[i]/base; 18 a[i]%=base; 19 } 20 } 21 void add(ll a[],ll b[],ll c[]) 22 { 23 reg ll x=0; reg int i; 24 c[0]=max(a[0],b[0]); 25 F(i,1,c[0]) 26 { 27 c[i]=a[i]+b[i]+x; 28 x=c[i]/base; 29 c[i]%=base; 30 } 31 if(x) 32 { 33 ++c[0]; 34 c[c[0]]=x; 35 } 36 while(c[c[0]]==0&&c[0]>1)--c[0]; 37 } 38 int main() 39 { 40 a[0]=1; a[1]=1; 41 b[0]=1; b[1]=1; 42 int n,m; reg int i; 43 scanf("%d%d",&n,&m); 44 F(i,1,n+1) dcheng(a,i); 45 F(i,n-m+4,n+2) dcheng(a,i); 46 dcheng(a,2*m); 47 F(i,1,n) dcheng(b,i); 48 F(i,n-m+4,n+3) dcheng(b,i); 49 dcheng(b,n*(n+1)); 50 add(a,b,c); 51 reg int l; 52 printf("%lld",c[c[0]]); 53 for(int i=c[0]-1;i>=1;--i) printf("%010lld",c[i]); 54 return 0; 55 }
View Code
Wow, wonderful blog format! How lengthy have you ever been running a
blog for? you made running a blog glance easy.
The total glance of your site is great, let alone
the content! You can see similar here sklep online
Thanks for some other informative web site.
The place else could I get that type of information written in such a perfect approach?
I have a venture that I am simply now operating on, and I
have been on the glance out for such information. I saw similar here:
Sklep internetowy
Howdy! Do you know if they make any plugins to help with SEO?
I’m trying to get my blog to rank for some targeted keywords but I’m not seeing very
good success. If you know of any please share.
Cheers! You can read similar text here: Ecommerce