HNOI2012排队

排列组合题(本文A(n,m)表示从n个元素里选m个的排列数)。

首先，老师和女生有不能相邻的限制条件，应该用插空法。而且老师人数较少且固定，把老师和男生进行混合，对女生用插空。

我先来一手错误做法，n个男生先全排列A(n,n)，两个老师插空A(n+1,2),m个女生插空A(n+3,m),乘到一起。ans=A(n,n)*A(n+1,2)*A(n+3,m)。试一下1，1;差了4。为什么呢？因为我们这种考虑方式忽略了只用一个女生将老师隔开的情况。

那这样就好说了，还是混合加插空，把老师和男生混在一起。

首先让两个老师站在一起2*A(n+1,n+1)，然后让任意一个女生将其隔开2*m*A(n+1,n+1)。此时这个整合体与男生共有n+2个空，插入剩下的m-1个女生，总共2*m*A(n+1,n+1)*A(n+2,m-1)。

接着让两个老师不站在一起，有两种计算方式：

（1）老师和男生一共A(n+2,n+2)中排列方式，减去上面的站在一起的方式，总共A(n+2,n+2)-2*A(n+1,n+1)。

（2）男生全排列A(n,n),老师插n+1个空，总共A(n,n)*A(n+1,2)。

上述两种方法得到的结果用排列恒等式是很容易证明相等的，自己想一想。插个图片，想看的可以看看。

剩下的女生插空A(n+3,m)，总共A(n+3,m)*A(n,n)*A(n+1,2)。

两种情况加在一起就是答案。

这题高精没跑了，但是为了少打高精组件，尝试化简，可以用一用上面证明图中的内容。再来张图：

得到结论((n+3)*n+2*m)*A(n+1,n+1)*A(n+2,m-1)。这东西就完全可以高精乘低精搞定了（其实只是少了个高精加……）。

#include<iostream>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<cstdio>

#include<vector>

#include<queue>

#include<stack>

using namespace std;

int a[]={,},len=;

void mult(int x){

    int res=;

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

        a[i]=a[i]*x+res;

        res=a[i]/;

        a[i]%=;

    }while(res){

        a[++len]=res%;

        res/=;

    }

}

void print(){

    for(int i=len;i>=;i--)

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

    return ;

}

int main(){

    int n,m;

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

    for(int i=;i<=n+;i++)

        mult(i);

    for(int i=n+;i>=n-m+;i--)

        mult(i);

    mult(n*n+*n+*m);

    print();

    return ;

}

巴特西

HNOI2012排队

最新文章

热门文章