結果

問題 No.836 じょうよ
ユーザー NoneNone
提出日時 2021-03-15 21:05:13
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 91 ms / 1,000 ms
コード長 3,526 bytes
コンパイル時間 230 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 93,056 KB
最終ジャッジ日時 2024-04-25 00:30:41
合計ジャッジ時間 3,901 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 81 ms
92,672 KB
testcase_01 AC 36 ms
52,352 KB
testcase_02 AC 39 ms
52,736 KB
testcase_03 AC 37 ms
52,480 KB
testcase_04 AC 36 ms
52,352 KB
testcase_05 AC 36 ms
52,352 KB
testcase_06 AC 40 ms
52,736 KB
testcase_07 AC 36 ms
52,608 KB
testcase_08 AC 36 ms
52,480 KB
testcase_09 AC 37 ms
52,352 KB
testcase_10 AC 37 ms
52,992 KB
testcase_11 AC 52 ms
65,664 KB
testcase_12 AC 55 ms
67,072 KB
testcase_13 AC 52 ms
65,664 KB
testcase_14 AC 51 ms
63,104 KB
testcase_15 AC 53 ms
66,176 KB
testcase_16 AC 91 ms
93,056 KB
testcase_17 AC 86 ms
91,008 KB
testcase_18 AC 53 ms
65,408 KB
testcase_19 AC 55 ms
68,992 KB
testcase_20 AC 68 ms
81,536 KB
testcase_21 AC 47 ms
62,080 KB
testcase_22 AC 55 ms
69,888 KB
testcase_23 AC 66 ms
78,848 KB
testcase_24 AC 55 ms
64,384 KB
testcase_25 AC 62 ms
70,144 KB
testcase_26 AC 50 ms
61,056 KB
testcase_27 AC 50 ms
61,440 KB
testcase_28 AC 54 ms
64,384 KB
testcase_29 AC 50 ms
63,872 KB
testcase_30 AC 50 ms
63,104 KB
testcase_31 AC 52 ms
66,304 KB
testcase_32 AC 53 ms
65,792 KB
testcase_33 AC 49 ms
63,232 KB
testcase_34 AC 52 ms
65,536 KB
testcase_35 AC 51 ms
65,792 KB
testcase_36 AC 53 ms
69,632 KB
testcase_37 AC 56 ms
69,504 KB
testcase_38 AC 59 ms
73,344 KB
testcase_39 AC 56 ms
71,296 KB
testcase_40 AC 65 ms
78,848 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class CycleGetter():

    def __init__(self,start,max_time):
        """
        :param max_time: 移動回数
        :param start: 初期条件
        :return front: cycleまでの要素のリスト
                cycle: cycle内の要素のリスト
                end: cycle後の余った部分の要素のリスト
                cnt: cycle回数
        """
        p = start
        front, cycle, end = [], [], []
        max_time+=1
        cnt = 0
        visit = {p:0}
        L, R =max_time,-1
        P = [p]
        for i in range(1,max_time):
            p = lift(p)
            if p in visit:
                """
                (L, R) = (サイクルに入るまでに移動した回数, サイクルの終端に着くまでに移動した回数)
                [6,2,3,4,0,1,2] ⇒ (L, R) = (1, 6)
                """
                L, R = visit[p], i
                period = R-L
                break
            visit[p] = i
            P.append(p)
        front = P[:L]
        if L != max_time:
            cycle, end = P[L:R],P[L:L+(max_time-L)%period]
            cnt =(max_time-L)//period
        self.front,self.cycle,self.end,self.cnt = front, cycle, end, cnt

    def apply(self,time):
        """
        :param time: time回進む
        :return:
        """
        if time<len(self.front):
            return self.front[time]
        else:
            time-=len(self.front)
            time%=len(self.cycle)
            return self.cycle[time]

    def set_sum(self):
        """
        区間　[0,r)　の累積和の求めるための前準備
        """
        def merge(x,y):
            return x+y

        self.front_sum=[0]
        for a in self.front:
            self.front_sum.append(merge(self.front_sum[-1],a))
        self.cycle_sum=[0]
        for a in self.cycle:
            self.cycle_sum.append(merge(self.cycle_sum[-1],a))

    def sum(self,r):
        """
        区間　[0,r)　の累積和の求める
        """
        res=0
        if r<=len(self.front):
            res+=self.front_sum[r]
        else:
            r-=len(self.front)
            p,q=r//len(self.cycle),r%len(self.cycle)
            res+=self.front_sum[-1]
            res+=self.cycle_sum[-1]*p+self.cycle_sum[q]
        return res

    def __getitem__(self, i):
        return self.apply(i)

    def __iter__(self):
        for i in range(max_time):
            yield self.apply(i)

    def __str__(self):
        res=[]
        for a in self:
            res.append(str(a))
        return " ".join(res)


################################################################################
def example():
    global input
    example = iter(
        """
30 30 11
        """
            .strip().split("\n"))
    input = lambda: next(example)

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

# example()

l,r,MOD=map(int,input().split())

#######################################
def lift(x):
    """ 写像を定義 """
    return (x+1)%MOD

start, max_time = l%MOD, r-l

CG=CycleGetter(start, max_time)
"""
備考
スタート地点が変わる場合はダブリング
スタート地点には作用がかかっていないため、スタート地点だけ性質が異なる場合がある点に注意
"""
front,cycle,end,cnt = CG.front, CG.cycle, CG.end, CG.cnt
#######################################


P=[0]*MOD
for x in front:
    P[x]+=1
for x in cycle:
    P[x]+=cnt
for x in end:
    P[x]+=1

print(*P,sep="\n")
0