N = 2019 cnt = [0] * N S = input() ans = 0 for s in S: s = int(s) new = [0] * N for n in range(N): idx = (10 * n + s) % N new[idx] += cnt[n] cnt = new cnt[s] += 1 ans += cnt[0] print (ans)
S = input() MOD = 2019 cnt = [0]*MOD cur = 0# 現在考えている部分文字列 cnt[cur] = 1# 部分文字列'0'も作れたと考える d = 1# 位を表す for s in S[::-1]: # 右から作る cur += int(s)*d # 新たな桁を追加 cur %= MOD cnt[cur] += 1 # 後処理 d *= 10# 位を上げる d %= MOD # ただし数が巨大になるため、計算量を減らすために剰余をとる ans = 0 for c in cnt: ans += c*(c-1)//2 print (ans)
N, M, S = map(int, input().split()) adj = [[] for _ in range(N)] for m in range(M): u,v,a,b = map(int, input().split()) u -= 1 v -= 1 adj[u].append((v,a,b)) adj[v].append((u,a,b))
C = [] D = [] for n in range(N): c, d = map(int, input().split()) C.append(c) D.append(d)
M = 2500 S = min(S, M-1) # 2500枚あれば十分 dist = [[INF]*M for _ in range(N)] # dist[都市][銀貨の枚数] dist[0][S] = 0 pq = [(0,S,0)] # (時間、銀貨の枚数、都市)
while pq: d, sil, node = heapq.heappop(pq) if dist[node][sil] < d: # 探索の対象にする必要があるか確認 continue # 銀貨に交換したとして、上限を超えないか、探索の必要があるか if sil+C[node] < M and d+D[node] < dist[node][sil+C[node]]: dist[node][sil+C[node]] = d + D[node] # 時間の更新 heapq.heappush(pq, (d + D[node], sil+C[node] ,node)) for next, a, b in adj[node]: # 銀貨が足りるか、探索の必要があるか if sil >= a and d + b < dist[next][sil-a]: dist[next][sil-a] = d + b heapq.heappush(pq, (d + b, sil-a ,next))
for i in range(1,N): print(min(dist[i])) # 残っている銀貨の枚数は問わない