문제링크

[[BRUTEFORCE|problem:BRUTEFORCE]]

현황

예제 케이스중 1,2,3번째는 똑같이 나오는데
예제 4번째 케이스가 틀리게 나옵니다. ㅜ

알고리즘 설명

링크
(사진이 커서 죄송합니다. 링크를 들어가시면 보실수 있습니다)

소스

~~~ py
import sys

sys.stdin = open('cases/bruteforce.txt')

cache = dict()

def normalize(num):
if num >= 1000000007:
num %= 1000000007
return num

for c in range(int(input())):
A, B, N = list(map(int, input().split()))

# AB 길이
ab_len = B - A + 1

# 초기화
s = 0
i = 0

# 첫번째 항
p = N
s += p
i += 1

# 일정항 까지의 합을 저장해둠. (마지막 연산을 위해서)
cache = dict()
cache[1] = N

while True:
    if i << 1 > ab_len:

        # 마지막 연산
        rest = ab_len - i
        rest_arr = list(bin(rest)[2:])
        i = 1
        s_part = 0
        for j in list(reversed(rest_arr)):
            if j == '1':
                s_part += cache[i]
            i <<= 1
        tmp = p * s_part
        tmp = normalize(tmp)
        s += tmp
        s = normalize(s)
        break

    else:
        tmp = p * s
        tmp = normalize(tmp)
        s += tmp
        s = normalize(s)
        i <<= 1
        cache[i] = s
        p = pow(p, 2)
        p = normalize(p)

# TODO: 최적화 해야함
# N 을 A - 1 번 곱한다.
base = 1
if A != 1:
    base = 1
    for i in range(1, A):
        base *= N
        base = normalize(base)
print(normalize(s * base))

기본 풀이

for c in range(int(input())):

A, B, N = list(map(int, input().split()))

a = pow(N, A)

b = 1

c = 1

for i in range(1, B - A + 1):

c *= N

b += c

normalize(b)

print(normalize(a * b))

</spoiler>