• 周五. 7月 1st, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

排队

admin

11月 28, 2021

题目描述

某中学有 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

发表评论

您的电子邮箱地址不会被公开。