[题解](排列组合)luogu_P3223排队

把老师和女生插到男生中间,先对男生排列:A(n,n),然后把老师插到n+1个空里:A(n+1,2),然后放入女生:A(n+3,m)

但是少考虑了老师之间由1个女生分开的情况,所以把三个人看作一个整体,内部也要排列一下,共A(n,n)*A(n+1,1)*A(2,2)*A(n+2,m-1)

用组合数同理

+高精

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
const int maxn=10009;
const ll base=100000;
int n,m;
struct bigint{
    ll num[10000],len;
    inline void clear(){
        memset(num,0,sizeof(num));
        len=0;
    }
    inline void give(int x){
        num[len=1]=x;
    }
    bigint operator *(const bigint&rhs)const{
        bigint ans;ans.clear();ans.len=len+rhs.len+10;
        for(int i=1;i<=len;i++)
        for(int j=1;j<=rhs.len;j++){
            ans.num[i+j-1]+=num[i]*rhs.num[j];
            ans.num[i+j]+=ans.num[i+j-1]/base;
            ans.num[i+j-1]%=base;
        }
        for(int i=1;i<=ans.len;i++)
        ans.num[i+1]+=ans.num[i]/base,ans.num[i]%=base;
        while(ans.len && !ans.num[ans.len])ans.len--;
        return ans;
    }
    bigint operator +(const bigint &rhs)const{
        bigint ans;ans.clear();ans.len=max(len,rhs.len)+10;
        for(int i=1;i<=ans.len;i++){
            ans.num[i]+=num[i]+rhs.num[i];
            ans.num[i+1]+=ans.num[i]/base;
            ans.num[i]%=base;
        }
        for(int i=1;i<=ans.len;i++)
        ans.num[i+1]+=ans.num[i]/base,ans.num[i]%=base;
        while(ans.len && !ans.num[ans.len])ans.len--;
        return ans;
    }
    inline void print(){
        printf("%lld",num[len]);
        for(int i=len-1;i>=1;i--)
        printf("%05lld",num[i]);
    }
}ans;
inline bigint cal(int n,int m){
    bigint ans,x;ans.clear();
    ans.give(1);
    if(!m)return ans;
    if(m>n){
        ans.clear();return ans;
    }
    for(ll i=n-m+1;i<=n;i++){
        x.give(i);ans=ans*x;
    }
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    ans=cal(n,n)*cal(n+1,2)*cal(n+3,m)+cal(n,n)*cal(n+1,1)*cal(2,2)*cal(m,1)*cal(n+2,m-1);
    ans.print();
}

 

上一篇:建外表实例


下一篇:如何从JavaScript中的BigInt获取数字?