HDU 5184 브 라켓 (카트란 수)

제목: LINK
제목: 합 법 적 인 괄호 서열 을 다음 과 같이 정의 합 니 다. ● 빈 시퀀스 는 합 법 적 인 괄호 시퀀스 ● s 가 합 법 적 인 괄호 서열 이 라면 (s) 도 합 법 적 인 괄호 서열 이다. ● a 와 b 가 합 법 적 인 괄호 서열 이 라면 ab 도 합 법 적 인 괄호 서열 이다. ● 합 법 적 인 괄호 서열 인 다른 경 우 는 없다. 이미 알 고 있 는 괄호 서열 의 앞부분 을 정 하고 얼마나 합 법 적 인 서열 을 구성 할 수 있 는 지 물 어보 세 요. n 을 홀수 로 하고 일부 괄호 를 정 하 는 등 불법 상황 을 미리 판단 할 수 있다.이후 합 법 적 인 학 열 수량 을 구하 다. 사실은 카 틀 란 드 수 를 구 하 는 거 야. 결과 ans = C (a + b, b) - C (a + b, b - 1), (a = 남 은 채 울 ')' 의 수량, b = 남 은 채 울 '(' 의 수량) - - ------------------------------------------------------------------------------------------------------------------------------------방안 수 는 C (n + m, m) - C (n + m, m - 1) 로 본 문제 가 위의 예 와 매우 비슷 하 다 는 것 을 알 수 있다.물론 이것 은 카 틀 란 드 수의 한 예 일 뿐 많은 용도 가 있 을 것 이다.위의 결과 에 대한 증명 과정: 평면 좌표계 에서 (0, 0) 에서 (n, m) 까지 매번 위로 올 라 가 거나 오른쪽으로 갈 수 있 으 며 x = y 의 직선 을 넘 지 못 하 는 방법 으로 바 뀔 수 있다.(0, 0) 과 (n, m) 를 모두 한 단위 로 (0, - 1), (n, m - 1) 로 옮 겨 라. (0, 0) 에서 (n, m) 까지 의 불법 수 = (0, - 1) 에서 (n, m - 1) 까지 의 과정 에서 적어도 한 점 과 x = y 가 교차 하 는 주 법 수.ans = 총 항목 - 불법 수량 = C (n + m, m) - 불법 수량.대칭 성에 따라 (0, - 1) 에서 (n, m - 1) 과정 에서 적어도 한 점 과 x = y 가 교차 하 는 주 법 수 = (- 1, 0) 에서 (n, m - 1) 까지 의 방법 수.그래서 ans = C (n + m, m) - C (n + m, m - 1).원제 로 돌아 가면 원제 결과 의 구법 은 좌표계 에 똑 같이 넣 고 합 법 적 인 서열 수 는 (x, y) = > (m, m) 이 며 x = y 의 수 를 넘 지 않 습 니 다. x 는 기 존 '(' 의 수, y 는 기 존 ') 의 수 입 니 다. m = n / 2;평이 와 대칭 성 을 통 해 우 리 는 구 (0, 0) = > (m - y, m - x) 가 x = y 직선 을 넘 지 않 는 방법 수로 전환 할 수 있 고 위 에서 구 한 공식 을 이용 할 수 있다.나눗셈 이 있 는 모델 링 을 사용 하기 때문에 역 원 을 요구 합 니 다.

/* ***********************************************
 	Author        : Napoleon
 	Mail		  : [email protected]
 	Created Time  : 2015-03-11 16:04:59
	Problem       : CB_32_C.cpp
************************************************ */
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std; 
#define INF 1000000000
typedef __int64 LL; 
#define N 1100111
#define mod 1000000007
LL n, a, b, fac[N]; 
char str[N]; 
void init() {
	fac[0] = 1; 
	for(int i = 1;i <= 1000111; i++) {
		fac[i] = (fac[i-1] * i) % mod; 
	}
}
LL pow_(LL a, LL b, LL m) {
	LL ret = 1; 
	while(b) {
		if(b&1) {
			ret *= a; ret %= m;  
		}
		a *= a; a %= m; 
		b >>= 1; 
	}
	return ret; 
}
LL Inv(LL a, LL m) {
	return pow_(a, m - 2, m); 
}
int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin); 
#endif // ONLINE_JUDGE
	init();
	while(scanf("%I64d", &n) != EOF) {
		scanf("%s", str); 
		if(n&1) {
			puts("0"); continue; 
		}
		a = b = 0; 
		int flag = 0; 
		for(int i = 0; str[i]; i ++) {
			if(str[i] == '(') a ++; 
			else b ++; 
			if(b > a) flag = 1; 
		}
		LL m = n / 2; 
		if(flag || a > m || b > m || b > a) {
			puts("0"); continue; 
		}
		a = m - a; b = m - b; 
		swap(a, b); //a >= b
		LL ans = (a-b+1)*fac[a+b] % mod; 
		ans = ans * Inv(a+1, mod) % mod; 
		ans = ans * Inv(fac[a], mod) % mod; 
		ans = ans * Inv(fac[b], mod) % mod; 
		cout<

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

Coq에서 증명된 이중 부정 주위의 증명

이중 부정 가져오기 이중 부정 해소를 증명할 수 없지만 삼중 부정 해소를 증명할 수 있다 이중 부정 해소의 이중 부정 이중 부정 해소와 배중률 동치 고전 이론을 얻으려면 직관주의 이론에 어느 것을 넣어도 된다는 것이...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

HDU 5184 브 라켓 (카트란 수)

좋은 웹페이지 즐겨찾기