[BOJ]伯俊1351号無限数列(Python)

質問する

無限数列Aは以下の通りです.

A0 = 1

Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1)

N,P,Qが与えられると,ANを取得するためのプログラムを作成する.

入力

第1行は、3つの整数N、P、Qを与える.

しゅつりょく

第1行出力AN.

制限

0 ≤ N ≤ 10¹²

2 ≤ P, Q ≤ 10⁹

例

入力

7 2 3

しゅつりょく

7

ヒント

滝滝xはxを超えない最大整数です.

に答える

import sys

def dfs(num):
    global P, Q, arr
    if num < 1:
        return 1
    elif num in arr:
        return arr[num]
    arr[num] = dfs(num//P) + dfs(num//Q)
    return arr[num]


if __name__ == "__main__":
    N, P, Q = map(int, sys.stdin.readline().split())
    arr = {}

    print(dfs(N))

arrをlist()に設定するとメモリを超えます.
リストを使用せずにcount変数を作成した後、dfsでnumが0の場合、countは1を増やすように行われると、ほとんどの場合良いですが、隠れたテストケースがあるようです.タイムアウトが発生しました.
そのため、ディクシャナを使ってこそ問題を正常に解決することができる.上のコードではA 0を単独で指定するのではなく,必要に応じて1を返す.