排队 题解 组合数学+高精度

因为实在是写不动了，所以菜鸡颓博客为了信奥发展的伟大未来作出一点小小的贡献

题目描述

某中学有 n 名男同学，m 名女同学和两名老师要排队参加体检。他们排成一条直线，并且任意两名女同学不能相邻，两名老师也不能相邻，那么一共有多少种排法呢？（注意：任意两个人都是不同的）

输入格式

只有一行且为用空格隔开的两个非负整数 n 和 m，其含义如上所述。
对于 30%的数据 n≤100,m≤100
对于 100%的数据 n≤2000,m≤2000

输出格式

输出文件 output.txt 仅包含一个非负整数，表示不同的排法个数。注意答案可能很大。

样例输入

1 1

样例输出

   12

题解：
这是一道组合数学，应该说是非常明显。
首先我们需要一个数奥生思路开始要正确。
我们选择固定男生和老师，然后将女生插空，貌似如果固定女生的式子会非常麻烦。我写到一半果断放弃了
固定男生时是A（n,n）;
固定老师时分两种情况:
老师卡在一起，也就是老师一起站在两个男生中间，是A（2，2），这时需要一个女生站在老师中间，总式子变成A(n,n)*(n+1)*A(2,2)*A(n+2,m-1),m-1在上面。
或者老师没有卡在一起,是A（n+1,2）,然后女生插空，总式子变成A(n,n)*A(n+1,2)*A(n+3,m).
合并式子，最终是n!*(2*m+n*(n+3))*(n+1)*(n+2)!/(n-m+3)!。

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 100010
using namespace std;
int n,m,a[maxn],b[maxn],c[maxn];
void mult(int a[],int b)
{
    int x=0;
    for(int i=1;i<=a[0];i++)
    {
        int tmp=a[i]*b+x;
        a[i]=tmp%10;
        x=tmp/10;
    }
    while(x)
    {
        a[++a[0]]=x%10;
        x/=10;
    }
}

int main()
{
    scanf("%d%d",&n,&m);a[0]=a[1]=1;
    for(int i=1;i<=n;i++) mult(a,i);
    mult(a,(2*m+n*(n+3)));
    mult(a,n+1);
    for(int i=n-m+4;i<=n+2;i++) mult(a,i);
    for(int i=a[0];i>0;i--) printf("%d",a[i]);
    return 0;
}

大概就是这样。