백준 9825 - MODSUM

https://www.acmicpc.net/problem/9825

 

문제를 보면 다음과 같이 언급하고 있다.

 

Important note: You can assume that the result will always be less than 1,000,000.

 

이 말을 통해 문제에서는 연산의 제한이 $10^{6}$임을 암시하고 있다.

 

문제에서 제시한 계산식

 

 \[\sum_{x_1 = v_1}^{w_1}\sum_{x_2 = v_2}^{w_2} \cdots \sum_{x_n = v_n}^{w_1} f(x_1, \dots, x_n)\] 

 

으로만 보면 많은 연산이 필요할 것으로 보이나, 제한을 걸고 있기 때문에 안심하고 브루트포스를 해도 되는 것으로 이해할 수 있다.

 

문제의 제한을 이해했으므로 나머지는 신경 쓸 필요 없이 문제에서 제시한 함수

 

 \[f(x_1, \dots, x_n) = \left(\left(\left(x_1 + x_2 + \dots + x_n\right)^4 + 2 \times \left(x_1 + x_2 + \dots + x_n \right)^2 \right) \mod {5} \right) + 1\] 

 

를 계산하면 문제 없이 정답을 받을 수 있다.

 

정답 코드 - python

def calc_poly(terms: list):
    poly_sum = sum(terms)
    ret = poly_sum ** 4
    ret += 2 * poly_sum ** 2
    ret %= 5
    return ret + 1
 
 
def solve():
    lt = list(map(int, input().split()))
    n = lt[0]
    idx = 1
 
    term_start = []
    term_cur = []
    term_last = []
    for i in range(n):
        term_start.append(lt[idx])
        term_cur.append(lt[idx])
        term_last.append(lt[idx + 1])
        idx += 2
 
    ans = 0
    while term_cur[0] <= term_last[0]:
        ans += calc_poly(term_cur)
        term_cur[n - 1] += 1
        for i in range(n - 1, 0, -1):
            if term_cur[i] > term_last[i] and i > 0:
                term_cur[i] = term_start[i]
                term_cur[i - 1] += 1
            else:
                break
    print(ans)
 
 
if __name__ == "__main__":
    solve()