even 하게 익은 SCON

• 에디토리얼 에는 DP 풀이, 조합론적 풀이, 일반항을 찾는 풀이가 모두 나와있다.
• DP풀이와 조합론적 풀이는 둘다 쉽게 떠올릴 수 있는 발상이다.
• DP로 풀 경우, 에디토리얼의 점화식을 그대로 따르면 O(n)이지만, 선형연립접화식이므로 행렬거듭제곱을 이용해서 최적화하면 O(logn)까지 단축시키는 것도 가능하다
  • O(n)에 풀면 352ms, O(logn)으로는 36ms가 걸렸다.
• 조합론적 풀이의 경우는, 거듭제곱과 combination을 모두 전처리해서 풀었을때 O(n)이 걸린다.
  • 처음에 내가 풀었던 방식도 이 방법이었는데, i<n 에 대해서 2^i 와 24^i를 구하는 것을 O(n)에 전처리해서 구하지 않고, 그냥 매번 계산하는 식으로 O(nlogn)에 구현했더니 python3에서는 시간초과가 났다. 거듭제곱을 전처리해서 O(n)으로 줄여도 908ms에 제법 아슬아슬하게 통과되었다.
• 일반항을 찾는 것도 가능하다는 것은, 뒤늦게 에디토리얼을 읽어보다가 배웠다. 사용하는 접근법이 상당히 신박하므로 한번 읽어보자. 이 방법도 빠른 거듭제곱을 사용하면 시간복잡도 O(logn)에 동작한다. 실제로는 32ms 에 통과되었다

"""Solution code for "BOJ 33913. even 하게 익은 SCON".

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

Tags: [combinatorics]
"""

MOD = 10**9 + 7


def main():
    N = int(input())

    dp_even, dp_odd = 1, 0
    for _ in range(1, N + 1):
        dp_even, dp_odd = (
            (24 * dp_even + 2 * dp_odd) % MOD,
            (24 * dp_odd + 2 * dp_even) % MOD,
        )

    print(dp_even)


if __name__ == '__main__':
    main()

"""Solution code for "BOJ 33913. even 하게 익은 SCON".

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

Tags: [combinatorics]
"""

from teflib import combinatorics

EVEN = 0
ODD = 1
MOD = 10**9 + 7


def main():
    N = int(input())

    coefs = {
        EVEN: [(24, -1, EVEN), (2, -1, ODD)],
        ODD: [(24, -1, ODD), (2, -1, EVEN)],
    }
    seeds = [[1, 0]]
    answer = combinatorics.multivariable_linear_recurrence(coefs, seeds, N, MOD)

    print(answer[EVEN])


if __name__ == '__main__':
    main()

"""Solution code for "BOJ 33913. even 하게 익은 SCON".

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

Tags: [combinatorics]
"""

from teflib import combinatorics


MOD = 10**9 + 7


def main():
    N = int(input())

    comb_calc = combinatorics.CombCalculator(MOD)
    pow_table_2 = [v := 1] + [v := (v * 2) % MOD for _ in range(1, N + 1)]
    pow_table_24 = [v := 1] + [v := (v * 24) % MOD for _ in range(1, N + 1)]

    answer = 0
    for sc in range(0, N + 1, 2):
        answer += (
            comb_calc.comb(N, sc) * pow_table_2[sc] * pow_table_24[N - sc] % MOD
        )

    print(answer % MOD)


if __name__ == '__main__':
    main()

"""Solution code for "BOJ 33913. even 하게 익은 SCON".

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

Tags: [math]
"""

MOD = 10**9 + 7


def main():
    N = int(input())
    answer = (pow(26, N, MOD) + pow(22, N, MOD)) * pow(2, -1, MOD) % MOD
    print(answer)


if __name__ == '__main__':
    main()

• Dependency:
  • teflib.combinatorics.CombCalculator
  • teflib.combinatorics.multivariable_linear_recurrence