• 周一. 5月 27th, 2024

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

《排队》有3个想法
  1. 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

  2. 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

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注