bzoj 2729: [HNOI2012]排队

2024-01-22 18:55:58

2729: [HNOI2012]排队

Time Limit: 10 Sec Memory Limit: 128 MB

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

题目分析

显然此题是一道组合题，我们先放男生，再分两种情况讨论。

当老师被男同学隔开时，有\(A_{n+1}^2\)种方案，此时老师便与男生等价。女生有\(A_{n+3}^m\)种方案。
当老师被女同学隔开时，有\(2 \times (n+1)\)种方案，此时老师中间必须有女生，所以女生必有一个在老师中，方案数为\(m \times A_{n+2}^{m-1}\)。

所以总方案数为\(n! \times (A_{n+1}^2 \times A_{n+3}^m + 2 \times (n+1) \times m \times A_{n+2}^{m-1})\)

蒟蒻高精度写挂了，查了好久才发现加法写挂，写完后发现被python操飞

#include <cstdio>

#include <cstring>

#define base 10000

struct bign{

    int len,a[10008];

    bign() {memset(a,0,sizeof a); len=1;}

    void Out() const {

        printf("%d",a[len]);

        for(int i=len-1;i;--i) printf("%04d",a[i]);

        puts("");

    }

    void clear() {memset(a,0,sizeof a); len=1;}

    void fo() {

        while(a[len+1])++len;

        while(!a[len]&&len>1)--len;

    }

    bign operator + (const bign &b) const {

        bign ret;

        ret.len=(len<b.len)?b.len:len;

        for(int i=1;i<=ret.len;++i) {

            ret.a[i]+=a[i]+b.a[i];

            if(ret.a[i] >= base) ++ret.a[i+1],ret.a[i]-=base;

        }ret.fo();

        return ret;

    }

    bign operator * (const int &b) const {

        bign ret; ret.len=len;

        for(int i=1;i<=len;++i) {

            ret.a[i]+=a[i]*b;

            ret.a[i+1]+=ret.a[i]/base;

            ret.a[i]%=base;

        }ret.fo();

        return ret;

    }

};

void A(int n,int m,bign &a) {

    if(n<m) a=a*0;

    else for(int i=n-m+1;i<=n;++i) a=a*i;

}

int main() {

    int n,m; bign a,b;

    scanf("%d%d",&n,&m);

    a.a[1]=1; b.a[1]=2;

    A(n+1,2,a); //a.Out();

    A(n+3,m,a); //a.Out();

    A(n+1,1,b); //b.Out();

    A(n+2,m-1,b); //b.Out();

    b=b*m; //b.Out();

    a=a+b; /*a.Out();*/ A(n,n,a);

    a.Out(); return 0;

}

def A(n,m):

    if n<m:

        return 0

    ret=1

    for i in range(n-m+1,n+1):

        ret *= i

    return ret

n,m=raw_input().split()

n=int(n)

m=int(m)

print (A(n,n)*(A(n+1,2)*A(n+3,m)+2*m*A(n+1,1)*A(n+2,m-1)))

码农公寓