2^30으로 나눈 나머지로 2^5으로 나눈 나머지를 구할 수 있을까

8672번: Drabina (acmicpc.net) 사다리의 맨 끝단 s까지 올라가는데 한걸음 혹은 두걸음씩 올라갈 수 있다 이 때 끝까지 올라가는 방법의 수를 $2^{p}$로 나눈 나머지를 구해야한다. 이것만 보면 매우 쉬운 문제다 dp[i] = i번째까지 올라가는 방법의 수하면 가능한 경우는 한걸음 혹은 두걸음이므로... dp[i] += dp[i-1]dp[i] += dp[i-2] 인 전형적인 문제 dp = [0]*(s+1)dp[0] = 1mod = 2**pfor i in range(1,s+1): for j in range(1,3): if i >= j: dp[i] += (dp[i-j]) dp[i] %= mod  문제는 최대 ..

• format_list_bulleted 정수론
• · 2024. 8. 10.
• textsms

분할정복을 이용한 거듭제곱 빠르게하기

1. 분할정복 문제를 더 이상 나눌 수 없을 때까지 더 작은 문제로 나누면서 이 작은 문제들을 각각 풀면서, 병합하여 전체 문제의 답을 구하는 알고리즘 divide - conquer - combine 방식으로 설계한다. 문제가 분할이 가능하면 2개 이상의 작은 문제로 나눈다(divide) 나누어진 문제가 분할이 가능하면, 또 다시 문제를 분할하고 그렇지 않으면 문제를 푼다(conquer) 푼 문제들을 통합하여 전체 문제의 답을 구한다(combine) 당연하지만 divide를 잘 하면 나누어진 문제를 푸는 것은 매우 쉬우므로 divide를 잘 하는 것이 중요하다 재귀알고리즘을 많이 사용하게 되는데, 이 때문에 오히려 효율적이지 못할 수 있다. 2. 응용 - 거듭제곱 n번의 거듭제곱은 자신을 n번 곱하므로 ..

• format_list_bulleted 분할 정복
• · 2022. 8. 15.
• textsms