bzoj 2729: [HNOI 2012] 줄 서기

전송 문:http://www.lydsy.com/JudgeOnline/problem.php?id=2729
사고방식: 간단 한 배열 조합 문제
A(n,n)*(A(n+1,2)*A(n+3,m)+A(m,1)*A(2,2)*A(n+1,1)*A(n+2,m-1))
우선 우 리 는 남 자 를 무제 한 으로 관찰 하고 남 자 를 먼저 A (n, n) 로 배치한다.
그리고 우 리 는 선생님 을 배정 하고 선생님 은 이웃 할 수 없습니다. n 명의 남학생 은 n + 1 개의 빈자리 가 있 습 니 다.
만약 선생님 이 남학생 에 게 분리 된다 면 A (n + 1, 2) 의 방안 이 있다.
지금 은 n + 3 의 빈자리 가 생 겼 고, 또 m 명의 여 자 를 풀 어 주어 야 한다.
즉, A (n + 3, m). 이것 이 바로 식 플러스 앞 부분 입 니 다.
그러나 여자 가 태 어 나 기 전에 선생님 은 이웃 할 수 있 습 니 다. 우리 뒤에 한 여자 로 격 리 만 하면 됩 니 다.
이렇게 하면 우 리 는 A (n, n) * A (2, 2) * A (m, 1) * A (n + 2, m - 1) 방안 이 있다.
즉, 두 선생님 의 순 서 를 매 거 하고 중간 에 있 는 여 자 를 매 거 하 며 마지막 으로 n + 2 개의 위치 (두 선생님 이 묶 여 있 습 니 다) 에 남 은 m - 1 명의 여 자 를 두 었 습 니 다.
만약 우리 가 먼저 여 자 를 배열 하고 선생님 을 배치한다 면, 우 리 는 여러 가지 상황 을 토론 할 것 이다.
남 자 를 배열 한 후에 두 명의 여자 가 인접 할 수 있 고 두 팀 이 있 을 수 있 으 며 각 조 의 두 여자 가 인접 할 수 있 고 세 명의 여자 가 인접 할 수 있 기 때문이다.
마지막 으로 두 명의 선생님 으로 그들 을 갈 라 놓 았 다.
뭐? 마지막 남자 라 고?사실 할 수도 있 지만, 토론 하기 가 비교적 복잡 할 뿐이다.
답 이 크 면 정밀도 가 높 으 면 된다.

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int maxl=10010,P=10000;
using namespace std;
int n,m;

struct bign{
	int v[maxl],len;
	void del0(){while (len>1&&!v[len-1]) len--;}
	void clear(){memset(v,0,sizeof(v)),len=1;}
	bign operator *(const bign &b){
		bign c;c.clear();
		c.len=len+b.len;
		for (int i=0;i<len;i++)
			for (int j=0;j<b.len;j++){
				c.v[i+j]+=v[i]*b.v[j];
				if (c.v[i+j]>P) c.v[i+j+1]+=c.v[i+j]/P,c.v[i+j]%=P;
			}
		c.del0();return c;
	}
	bign operator +(const bign &b){
		bign c;c.clear();
		c.len=max(len,b.len)+1;
		for (int i=0;i<c.len;i++){
			c.v[i]+=v[i]+b.v[i];
			if (c.v[i]>P) c.v[i+1]++,c.v[i]-=P;
		}
		c.del0();return c;
	}
	void write(){
		printf("%d",v[len-1]);
		for (int i=len-2;i>=0;i--) printf("%04d",v[i]);
		puts("");
	}
};

bign fact(int a,int b){
	bign res;res.clear();
	if (a>b) return res;
	res.v[0]=1;
	for (int i=a;i<=b;i++){
		bign pp;pp.clear(),pp.v[0]=i;
		res=res*pp;
	}
	return res;
}
bign A(int n,int m){
	if (!m){
		bign res;res.clear(),res.v[0]=1;
		return res;
	}
	if (m>n){bign res;res.clear();return res;}
	return fact(n-m+1,n);
}
//A(n,n)*(A(n+1,2)*A(n+3,m)+A(m,1)*A(2,2)*A(n+1,1)*A(n+2,m-1))

int main(){
	scanf("%d%d",&n,&m);
	bign ans=A(n,n)*(A(n+1,2)*A(n+3,m)+A(m,1)*A(2,2)*A(n+1,1)*A(n+2,m-1));
	ans.write();
	return 0;
}