Luogu P3223 [HNOI2012]排队组合

本来做了一道 P4901 排队后来发现自己做错题了。。。到也都是数学qwq

这题最恶心的就是两只（雾）老师。

那我们分类讨论：

1.两个老师之间是男生：

　　$ A(n,n)*A(n+1,2)*A(n+3,m) $

首先男生有$ A(n,n)=n! $种排列方式;然后有$ n+1$ 个空隙（加上开头和结尾）可以放老师，所以老师是$ A(n+1,2)=(n+1)!/(n+1-2)!=(n+1)*n$;然后有$ n+3$ 个空隙（加上开头和结尾）可以放女生，所以女生是$ A(n+3,m)=\frac{(n+3)!}{(n+3-m)!}$

2.两个老师之间是女生（相当于捆绑）：
　　$A(n,n)*A(2,2)*m*A(n+1,1)*A(n+2,m-1)$

首先男生有$ A(n,n)=n! $种排列方式；老师按先后分有$A(2,2)=2$种排列；然后女生中任取$1$个有$m$种；然后有$ n+1$ 个空隙（加上开头和结尾）可以放老师+女生+老师(捆绑)，所以老师+女生+老师一个整体的位置是$ A(n+1,1)=(n+1)!$；然后有$ n+2$ 个空隙（加上开头和结尾，并且老师+女生+老师看作一个整体）可以放$m-1$女生，所以女生是$ A(n+2,m-1)=\frac{(n+2)!}{(n+3-m)!}$

所以原式：$A(n,n)*A(n+1,2)*A(n+3,m)+A(n,n)*A(2,2)*m*A(n+1,1)*A(n+2,m-1)$

化简可得：$\frac{(n+1)!*(n+2)*(n^2+3*n+2*m)}{(n+3-m)!}$

然后自己死在了scanf上：少写了一个%d...fk

#include<cstdio>

#include<iostream>

#define R register int

using namespace std;

const long long B=10000000000ll;

int n,m,sz=;

long long ans[];

inline void mul(int x) { R tmp=;

    for(R i=;i<=sz;++i) ans[i]*=x,ans[i]+=tmp,tmp=ans[i]/B,ans[i]%=B;

    if(tmp) ++sz,ans[sz]=tmp;

}

signed main() {

    scanf("%d%d",&n,&m); ans[]=;

    for(R i=;i<=n+;++i) mul(i); mul(n*(n+)+*m);

    for(R i=n-m+;i<=n+;++i) mul(i); //cout<<sz<<endl;

    printf("%lld",ans[sz]); for(R i=sz-;i;--i) printf("%010lld",ans[i]); putchar('\n');

}

2019.05.17

巴特西

Luogu P3223 [HNOI2012]排队组合

最新文章

热门文章

巴特西

Luogu P3223 [HNOI2012]排队 组合

最新文章

热门文章

Luogu P3223 [HNOI2012]排队组合