結果
問題 | No.1097 Remainder Operation |
ユーザー |
|
提出日時 | 2024-01-05 17:06:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 150 ms / 2,000 ms |
コード長 | 3,543 bytes |
コンパイル時間 | 255 ms |
コンパイル使用メモリ | 82,212 KB |
実行使用メモリ | 116,060 KB |
最終ジャッジ日時 | 2024-09-27 19:08:04 |
合計ジャッジ時間 | 5,644 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 21 |
ソースコード
class CycleGetter():def __init__(self,start,max_time):""":param max_time: 移動回数:param start: 初期条件:return front: cycleまでの要素のリストcycle: cycle内の要素のリストend: cycle後の余った部分の要素のリストcnt: cycle回数"""p = startfront, cycle, end = [], [], []max_time+=1cnt = 0visit = {p:0}L, R =max_time,-1P = [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], iperiod = R-Lbreakvisit[p] = iP.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)//periodself.front,self.cycle,self.end,self.cnt = front, cycle, end, cntdef 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+A[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=0if 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 resdef __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 inputexample = iter("""2314159 1414211271828""".strip().split("\n"))input = lambda: next(example)################################################################################import sysinput=sys.stdin.readline# example()N=int(input())A=list(map(int, input().split()))#######################################def lift(x):""" 写像を定義 """return (x+A[x%N])%Nstart, max_time = 0, 10**13CG=CycleGetter(start, max_time)"""備考スタート地点が変わる場合はダブリングスタート地点には作用がかかっていないため、スタート地点だけ性質が異なる場合がある点に注意"""front,cycle,end,cnt = CG.front, CG.cycle, CG.end, CG.cnt#######################################CG.set_sum()Q=int(input())for _ in range(Q):K=int(input())print(CG.sum(K))