結果

問題 No.1013 〇マス進む
コンテスト
ユーザー None
提出日時 2021-10-29 14:42:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 560 ms / 2,000 ms
コード長 1,892 bytes
コンパイル時間 525 ms
コンパイル使用メモリ 82,076 KB
実行使用メモリ 247,168 KB
最終ジャッジ日時 2024-10-07 08:33:52
合計ジャッジ時間 20,243 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 62
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Doubling:
    def __init__(self, A, K_max=10**18 + 1):
        """
        :param A: 初期条件（写像 A:i->j を定義）
        :param K_max: K_max まで参照する可能性がある

        doubling[i][k] := dp[2^i][k]

        ダブリングを考える際、初期値は[0,1,2,....,N-1] (=dp[i][k] の添え字 k)と考えるべき
        """
        self.k_max = K_max.bit_length()
        self.n = len(A)
        self.doubling = [[-1] * self.n for _ in range(self.k_max)]
        self.doubling[0]=A

        for i in range(1, self.k_max):
            self.doubling[i] = self.merge(self.doubling[i-1],self.doubling[i-1])

    def merge(self,dp_i,dp_j):
        """
        :return dp[i+j] = merge(dp[i],dp[j])
        """
        dp_ij=[0]*self.n
        for k in range(self.n):
            if dp_j[k]!=-1:
                dp_ij[k]=dp_i[(dp_j[k]+k)%N] + dp_j[k]
        return dp_ij

    def apply_all(self, K):
        """
        :param K: K回進む
        0~N-1の全ての要素を同時にK回進める
        ダブリングを考える際、初期値は[0,1,2,....,N-1] (=dp[i][k] の添え字 k)と考えるべき
        """
        res=P
        for k in range(K.bit_length()):
            if K&(1<<k):
                res = self.merge(self.doubling[k],res)
        return res

################################################################################
def example():
    global input
    example=iter(
        """
5 2
1 2 3 4 5

        """
            .strip().split("\n"))
    input=lambda:next(example)

"""
1->3->4->1->3->4
"""

################################################################################
import sys
input = sys.stdin.readline

# example()

N, K = map(int, input().split())
P = list(map(int, input().split()))

doubling = Doubling(P, K_max = 10**18 + 1)
res=doubling.apply_all(K-1)
for i,r in enumerate(res):
    print(i+r+1)
0