[python]Can you sum?

https://www.codewars.com/kata/638bc5d372d41880c7a99edc/train/python

Codewars - Achieve mastery through coding practice and developer mentorship

 이 문제는 알고리즘 문제라기보다 수학 문제입니다. n을 입력받을 때 아래의 식의 답을 구하는 것입니다. 답이 클 경우 10의 9+7로 나눈 나머지 값을 답으로 합니다. n의 범위가 2에서 10의 18승이기 때문에 반복문을 이용하면 큰 수의 경우 시간이 오래 걸립니다. 시간을 단축하기 위해서는 수열 합의 식을 일반 함수 식으로 변경해야 합니다.

 일반 함수 식으로 변경하는 풀이법은 다음과 같습니다.

 이 식을 적용하면 다음과 같습니다. 

def f(n:int) -> int:
    m = pow(10, 9)+7
    return 2 * (pow(2, n, m) * (n * n - 2 * n + 3) - 3) % m

👀 pow(2, n, m)을 사용한 이유는 2의 n승의 경우 값이 크기 때문에 미리 지정되어있는 수로 나누면 시간을 단축할 수 있습니다.