結果

問題 No.1097 Remainder Operation
コンテスト
ユーザー norioc
提出日時 2026-01-20 20:45:41
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 1,143 ms / 2,000 ms
コード長 1,137 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 347 ms
コンパイル使用メモリ 82,628 KB
実行使用メモリ 311,812 KB
最終ジャッジ日時 2026-01-20 20:45:57
合計ジャッジ時間 15,076 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

class DoublingDP:
    def __init__(self, xs: list, f0, op, nb=60):
        size = len(xs)
        doubling = [[0] * size for _ in range(nb)]
        dp = [[0] * size for _ in range(nb)]
        for i in range(size):
            doubling[0][i] = xs[i]
            dp[0][i] = f0(i)

        for k in range(nb-1):
            for i in range(size):
                doubling[k+1][i] = doubling[k][doubling[k][i]]
                dp[k+1][i] = op(dp[k][i], dp[k][doubling[k][i]])

        self.nb = nb
        self.doubling = doubling
        self.dp = dp
        self.op = op

    def query(self, k: int, start: int, init):
        cur = start
        val = init
        for i in range(self.nb):
            if k & (1 << i):
                val = self.op(val, self.dp[i][cur])
                cur = self.doubling[i][cur]

        return cur, val


def f(p: int) -> int:
    return A[p]


def op(a, b):
    return a + b


N = int(input())
A = list(map(int, input().split()))

xs = [(i + A[i]) % N for i in range(N)]
d = DoublingDP(xs, f, op)
Q = int(input())
for _ in range(Q):
    K = int(input())
    _, val = d.query(K, 0, 0)
    print(val)
0