首页 > 代码库 > [BZOJ 2729][HNOI2012]排队（排列组合+高精）
[BZOJ 2729][HNOI2012]排队（排列组合+高精）
Description
某中学有 n 名男同学，m 名女同学和两名老师要排队参加体检。他们排成一条直线，并且任意两名女同学不能相邻，两名老师也不能相邻，那么一共有多少种排法呢？（注意：任意两个人都是不同的）
Solution
好像必须写压位高精的QAQ
先排n名男生，插空，讨论两名老师插在两个不同的空里的情况和先排在一起再在中间插一名女生的情况
#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>typedef long long LL;using namespace std;struct Bign{ static const int base=100000; static const int width=5; LL len,s[10010]; Bign() {memset(s,0,sizeof(s));len=1;} Bign(int num){*this=num;} void clear(){while(len>1&&!s[len-1])len--;} Bign operator = (int num) { len=0; while(num) { s[len++]=num%base; num/=base; } return *this; } Bign operator + (const Bign& b) { Bign c;c.len=0; for(int i=0,g=0;g||i<max(len,b.len);i++) { int x=g; if(i<b.len)x+=b.s[i]; if(i<len)x+=s[i]; c.s[c.len++]=x%base; g=x/base; } return c; } Bign operator * (const Bign& b) { Bign c;c.len=len+b.len; for(int i=0;i<len;i++) { for(int j=0;j<b.len;j++) { c.s[i+j]+=s[i]*b.s[j]; } } for(int i=0;i<c.len;i++) { c.s[i+1]+=c.s[i]/base; c.s[i]%=base; } c.clear(); return c; } Bign operator * (const int& b) { Bign c; c.len=0; for(int i=0,g=0;g||i<len;i++) { int x; if(i<len)x=s[i]*b+g; else x=g; c.s[c.len++]=x%base; g=x/base; } return c; } void print() { string res; printf("%d",s[len-1]); for(int i=len-2;i>=0;i--) printf("%05d",s[i]); }};Bign A(int x,int y){ if(x>y)return Bign(); Bign c=1; for(int i=y-x+1;i<=y;i++) c=c*i; return c;}int n,m;int main(){ scanf("%d%d",&n,&m); Bign ans; 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(); return 0;}
[BZOJ 2729][HNOI2012]排队（排列组合+高精）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。