비요뜨의 징검다리 건너기

ps
링크	acmicpc.net/…
출처	BOJ
문제 번호	18291
문제명	비요뜨의 징검다리 건너기
레벨	골드 5
분류	조합론
시간복잡도	O(T*logn)
인풋사이즈	T<=1000, n<=10^9
사용한 언어	Python 3.11
제출기록	31256KB / 48ms
최고기록	44ms
해결날짜	2023/02/13

풀이

1번과 N번 사이에 있는 징검다리를 원하는 만큼 밟고 갈수 있다.
따라서 {2, … ,N-1}의 부분집합의 갯수를 구하는 문제가 된다. 답은 2^(N-2) % MOD. 거듭제곱의 빠른 계산 (Exponentiation by squaring)을 이용하면 O(logN)에 구할수 있다.
- N=1일때에는 1을 출력하는 것만 신경써주면 된다

코드

"""Solution code for "BOJ 18291. 비요뜨의 징검다리 건너기".

- Problem link: https://www.acmicpc.net/problem/18291
- Solution link: http://www.teferi.net/ps/problems/boj/18291
"""

import sys

MOD = 10**9 + 7


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        N = int(sys.stdin.readline())
        print(1 if N == 1 else pow(2, N - 2, MOD))


if __name__ == '__main__':
    main()

BOJ, 골드 5