기록방

👉 문제링크 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net 🔸 문제 분석 🔸 주사위 M개에 대해 i번째 주사위의 면 개수는 Ni, 면의 모든 값의 총합은 Si로 입력된다. 모든 주사위를 던졌을 때의 기대값을 계산한다. S1/N1 + S2/N2 + ... + SM/NM 계산의 어려움 때문에 임의의 분수 a / b를 모듈러를 이용해 (a * b-1 mod x)의 정수 값으로 계산한다. 🔸 문제 풀이 🔸 문제의 수학 이론 설명이 꽤 길지만, 읽어보면 이해 못할 정도는 아니다. 보다 정확한 확률 계산을 위해 모듈러 표현 방식을 사용한다는 것이다. 문제에서 제시된 공식을..

👉 문제링크 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 🔸 문제 분석 🔸 피보나치 수열을 구현하는데 n이 1,000,000,000,000,000,000 으로 매우 큰 수가 주어진다. 🔸 문제 풀이 🔸 피보나치 수열을 구현하는데 반복문, 재귀, 동적 계획법을 사용할 수 있지만, 매우 큰 n에 대해서는 분할 정복을 이용한 거듭제곱을 이용해야한다. 행렬 곱셈을 이용한다. n번째 피보나치수는 (n/2-1)번째 피보나치 수[k1]와 (n/2)번째 피보나치 수[k2], (n/2+1)번째 피보나치 수[k3], (n/2+2)번째 피보나치 수[k4]로 나타낼 수 있다. EX ) 0, 1, 1, 2,..