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] = 1

mod = 2**p

for i in range(1,s+1):
    
    for j in range(1,3):
        
        if i >= j:

            dp[i] += (dp[i-j])
            dp[i] %= mod

 

 

문제는 최대 $10^{6}$개의 s,p가 쿼리로 주어지는데 s도 10^6이라서 매번 이러면 불가능하다...

 

그러면 뭐 10^6에 대해 dp 테이블 한번만 채우고... s,p 주어질때마다 dp[s] % 2**p로 한다면?

 

이랬더니 메모리 초과나더라고

 

dp = [0]*(10**6+1)
dp[0] = 1

for i in range(1,10**6+1):
    
    for j in range(1,3):
        
        if i >= j:

            dp[i] += (dp[i-j])

z = int(input())

for _ in range(z):
    
    s,p = map(int,input().split())
    
    print(dp[s] % (2**p))

 

 

그러면 역시 처음에 dp테이블 채울때 mod로 나눠놔야한다는 소리인데... p가 매번 달라지는데 가능한건가???

 

x를 m1으로 나눈 나머지가 a라고 해보자.

 

x = p * m1 + a

 

만약 m1이 m2로 나눠진다고 할 때 x를 m2로 나눈 나머지는?

 

m1이 m2로 나누어 떨어지므로 양변을 m2로 나눠보면..?

 

p*m1이 m2로 나누어 떨어지기 때문에 a를 m2로 나눈 나머지가 x를 m2로 나눈 나머지와 같다.

 

따라서 x를 m1으로 나눈 나머지를 알고 있을 때, m1이 m2로 나누어 떨어진다면, x를 m2로 나눈 나머지는...

 

x를 m1으로 나눈 나머지를 m2로 나눈 나머지와 같다

 

따라서 p의 최댓값이 $2^{30}$이므로 한번 dp를 채울때 $2^{30}$으로 나눈 나머지를 구해놓는다면...

 

매 쿼리마다 s,p가 주어질때, dp[s] % 2**p를 구하면 된다

 

from sys import stdin

dp = [0]*(10**6+1)
dp[0] = 1

mod = 2**30

for i in range(1,10**6+1):
    
    for j in range(1,3):
        
        if i >= j:

            dp[i] += (dp[i-j])
            dp[i] %= mod

z = int(stdin.readline())

for _ in range(z):
    
    s,p = map(int,stdin.readline().split())
    
    print(dp[s] % (2**p))