kinssang   4년 전

점화식이 이상한데 설명하자면 이렇습니다

예시) N = 5, L = 2, R = 2인 경우의 답을 구해보자.


5의 가능한 위치는 L = 2 부터 N-R+1 = 3까지


1. 5의 위치가 2일때

편의상 배치를 ㅁ5ㅁㅁㅁ으로 나타내자.

ㅁ5ㅁㅁㅁ 왼쪽 ㅁ에 들어갈 숫자를 정하는 경우의 수는  4C1, 그리고 왼쪽의 ㅁ5를 완성하는데 가능한 경우는

N=2 일 때 L = 2, R = 1인 경우와 같다. 그리고 오른쪽 5ㅁㅁㅁ을 완성하는데 가능한 경우는 N=4일 때, L=1, R = 2인 경우와 같다.

따라서 4 * 1 * 2 = 8


2. 5의 위치가 3일때

ㅁㅁ5ㅁㅁ 5의 왼쪽인 ㅁㅁ에 들어갈 숫자를 정하는 경우의 수는 4C2, 그리고 왼쪽의 ㅁㅁ5를 완성하는데 가능한 경우는

N=3 일 때, L = 2, R = 1인 경우와 같고, 5ㅁㅁ을 완성하는 경우의 수는 N=3일때 L=1, R= 2인 경우와 같다.

따라서 6*1*1 = 6


3. 5의 위치가 4일때

1번과 대칭이므로 생략하겠습니다. 본 소스에선 계산을 합니다.


아무래도 곱셈연산의 나머지 연산에서 뭔가 문제가 생긴 듯 한데

제가 데이터 타입을 unsigned long long 으로 선언해서 1000000007 * 1000000007해도 unsigned long long 최대범위보다 작으므로 두 수끼리 곱할때마다 나머지 연산 해주면 아무 문제 없이 작동할 것 같았거든요.


혹시 어떤 문제가 있는지 가르쳐주시면 감사하겠습니다.

kinssang   4년 전

괄호 순서가 틀렸었네요.

ygonepiece   9달 전

100 2 2

598881956

100 50 51
769496025

100 51 50
769496025

100 52 50
0

ygonepiece   9달 전

100 1 2
990953332

100 2 1
990953332

댓글을 작성하려면 로그인해야 합니다.