排队（排列组合） | Hexo

归档于 2019-06-27 11:15

题目大意：

两个老师，n个男，m个女，女不互邻，老师不互邻 方案

不是${A_n^n}{A_{n+1}^m}{A_{n+m+1}^2}$，也不是${A_n^n}{A_{n+1}^2}{A_{n+3}^m}$

因为这两种都没有考虑两个老师||两个女生互邻然后中间再插一个（挡板法默认不相邻）

首先用${A_{n+1}^{n+1}}$$*$ ${A_{n+2}^{m-1}}$$m2$求出老师老师之间插男生时情况

那么应该再加上两个老师之间插一个女生

首先默认两个老师相邻因为两个老师不同，所以有两种情况${A_2^2}$，然后中间塞一个女生有m种情况;

然后把“”老师“”–“”女生“”–“”老师“”看作一个组合体即看成一个男生

然后剩余m-1个女生往n+2个空里插

所得${A_{n+1}^{n+1}}$$*$$A_{n+2}^{m-1}$$m2$``

最终相加得到$ans=$${A_n^n}{A_{n+1}^2}{A_{n+3}^m}$$+$${A_{n+1}^{n+1}}$$*$$A_{n+2}^{m-1}$$m2$

以下是本人丑陋的代码

#include<bits/stdc++.h>
#define ll long long
#define N 10000
#define P 4
using namespace std;
ll n,m;
struct bignum
{
    ll n[20000],l;
    bignum(){l=1,memset(n,0,sizeof(n));}
    void clear(){while(l>1&&!n[l-1]) l--;}
    void print()
    {
        printf("%lld",n[l-1]);
        for(ll i=l-2;i>=0;i--)
        printf("%0*lld",P,n[i]);
        printf("\n");
    }
    bignum operator = (ll x)
    {
        l=0;    
        while(x)
        {
            n[l++]=x%N;
            x/=N;
        }
        return *this;
    }
    bignum operator +(bignum x) const
    {
        bignum t=*this;
        if(x.l>t.l) t.l=x.l;        
        for(ll i=0;i<t.l;i++)
        {
            t.n[i]+=x.n[i];
            if(t.n[i]>=N)
            {
                t.n[i+1]+=t.n[i]/N;
                t.n[i]%=N;
            }
        }
        return t;
    }
       bignum operator * (const ll& b)
      {
        bignum c;
           c.l=0;
        for(ll i=0,g=0;g||i<l;i++)
        {
            ll x;
            if(i<l)x=n[i]*b+g;
            else x=g;
            c.n[c.l++]=x%N;
            g=x/N;
        }
        return c;
    }
    bignum operator *(bignum x) const
    {
        bignum t=*this,tep;
        tep.l=t.l+x.l;
        for(ll i=0;i<t.l;i++)
            for(ll j=0;j<=x.l;j++)
            {
                tep.n[i+j]+=t.n[i]*x.n[j];
            }
        for(ll i=0;i<tep.l;i++)
        {
            tep.n[i+1]+=tep.n[i]/N;
            tep.n[i]%=N;
        }
        tep.clear();
        return tep;
    }    

    bool operator <(bignum x) const
    {
        bignum t=*this,tep;
        if(t.l!=x.l)    return t.l<x.l;
        for(ll i=t.l-1;i>=0;i--)
        {
            if(t.n[i]!=x.n[i]) return t.n[i]<x.n[i];
        }
        return 0;
    }
    bool operator >(bignum x) const
    {
        bignum t=*this;
        if(t.l!=x.l) return t.l>x.l;
        for(ll i=t.l-1;i>=0;i--)
        {
            if(t.n[i]!=x.n[i]) return t.n[i]>x.n[i];
        }
        return 0;
    }
    bignum operator -(bignum x) const
    {
        bignum t=*this;
        if(t<x) printf("-");swap(t,x);
        ll jie=0;
        for(ll i=0;i<t.l;i++)
        {
            t.n[i]-=x.n[i];
            while(t.n[i]<0)
            {
                t.n[i]+=N;
                jie++;
            }
            t.n[i+1]-=jie;
            jie=0;
        }
        while(!t.n[t.l-1]&&t.l>1) t.l--;
        return t;
    }

}ans,c;
bignum A(ll m,ll n)
{
//    if(m>n) return bignum();
    bignum c;
    c=1;
    for(ll i=n-m+1;i<=n;i++)
        c=c*i;
    return c;
}
int main()
{
    cin>>n>>m;
    ans=0;
    ans=A(n,n)*(A(2,n+1)*A(m,n+3)+A(1,n+1)*A(2,2)*A(1,m)*A(m-1,n+2));
    ans.print();
}

View Code