import itertools N, M, Q = map(int,input().split()) query = [] for q in range(Q): a,b,c,d = map(int,input().split()) a-=1 b-=1 query.append((a,b,c,d)) mx = 0 for comb in itertools.combinations_with_replacement([i for i in range(1,M+1)],N): score = 0 for a,b,c,d in query: if (comb[b] - comb[a] == c): score += d mx = max(score,mx) print (mx)
N = int(input()) A = [0] + list(map(int,input().split()))
adj = [[] for n in range(N+1)] for n in range(N-1): u, v = map(int,input().split()) adj[u].append(v) adj[v].append(u)
ans= [0for i in range(N+1)] depth = [-1for n in range(N+1)] defdfs(s, d, dp):# 頂点番号、深さ、LIS depth[s] = d idx = bisect.bisect_left(dp,A[s]) history = dp[idx] # 巻き戻すために保存 dp[idx] = A[s] ans[s] = bisect.bisect_left(dp, INF) for i in adj[s]: if depth[i]==-1: dfs(i, d+1, dp) dp[idx] = history # 探索が終わったら巻き戻す dp = [INF] * len(A) dfs(1, 0, dp) for n in range(1,N+1): print(ans[n])
MOD = 10**9+7 X, Y = map(int, input().split()) if (X > Y): X, Y = Y, X if (X+Y)%3 != 0: print (0) exit() if (2*X < Y): print (0) exit() W = X - ((X+Y)//3) H = Y - ((X+Y)//3) mx = 10**6 fact = [1] * (mx+1) # 階乗を格納するリスト definv(n):# MODを法とした逆元 return pow(n, MOD-2, MOD) for i in range(mx): fact[i+1] = fact[i] * (i+1) % MOD # 階乗を計算 ans = (fact[W+H] * inv(fact[W]) * inv(fact[H])) % MOD # comb(W+H,W) = (W+H)!/(W!H!) print (ans)
さて次はa^(p-2) mod pを求めれば良いですが、この問題ではpは巨大であるため、先にa^(p-2)を計算してから剰余を取ろうとすると、計算効率が著しく悪くなります。そこで、計算の最中に随時剰余の計算を行う必要があります。Pythonの場合は、この処理をpow(a,p-2,p)とすることで計算できます。
コード
1 2 3 4 5 6 7 8 9 10 11 12
MOD = 10**9+7 W, H = map(int, input().split()) W-=1# コードを見やすくする H-=1# コードを見やすくする mx = 2*10**5 fact = [1] * (mx+1) # 階乗を格納するリスト definv(n):# MODを法とした逆元 return pow(n, MOD-2, MOD) for i in range(mx): fact[i+1] = fact[i] * (i+1) % MOD # 階乗を計算 ans = (fact[W+H] * inv(fact[W]) * inv(fact[H])) % MOD # comb(W+H,W) = (W+H)!/(W!H!) print (ans)
from itertools import accumulate MOD = 10**9+7 N, Q = map(int, input().split()) A = list(map(int, input().split())) C = list(map(int, input().split()))
D = [0] for n in range(N-1): d = pow(A[n],A[n+1],MOD) # pow(A[n],A[n+1])%MOD より高速 D.append(d) acc = list(accumulate(D)) # 累積和
C.insert(0,1) # 始点 C.append(1) # 終点 ans = 0 for q in range(len(C)-1): ans += abs(acc[C[q+1]-1]-acc[C[q]-1]) % MOD print (ans%MOD) # 最後のMODを忘れずに
N = int(input()) n = N ans = [] for i in range(2,int(N**0.5)+1): # intに変換すること while(n%i==0): n //= i # 整数除算(//)を使うこと ans.append(i) if n!=1: ans.append(n) ans = [str(a) for a in ans] ans = str(N)+": " + " ".join(ans) print (ans)
for i in range(2,N+1): if dp[i]: for j in range(i*i, N+1, i): dp[j] = 0 like2017 = [0] * (N+1) for n in range(N+1): if dp[n]==0: continue query = (n+1)//2 if dp[query]==1: like2017[n] = 1
for n in range(N): like2017[n+1] += like2017[n]
Q = int(input()) for q in range(Q): l, r = map(int,input().split()) print (like2017[r]-like2017[l-1])
import bisect N = 10**6 dp = [1] * (N+1) dp[0] = dp[1] = 0 prime = [] for i in range(2,N+1): if dp[i]: for j in range(i*i, N+1, i): dp[j] = 0 for n in range(N+1): if dp[n]: prime.append(n)
like2017 = [] for p in prime: query = (p+1)//2 idx = bisect.bisect_left(prime, query) if prime[idx] == query: like2017.append(p) Q = int(input()) for q in range(Q): l, r = map(int,input().split()) l = bisect.bisect_left(like2017, l) r = bisect.bisect_right(like2017, r) print (r-l)
import heapq N = int(input()) X = [] # ソートするためのリスト Y = [] for n in range(N): x, y = map(int,input().split()) X.append((x, n)) # 座標と街番号 Y.append((y, n)) X.sort() # 座標でソート Y.sort() adj = [ [] for v in range(N)] for n in range(N-1): # 数直線上で隣接している街と街の座標の差分を求める cost = X[n+1][0] - X[n][0] # まずはx adj[X[n+1][1]].append((cost, X[n][1])) # (辺のコスト, to街番号) adj[X[n][1]].append((cost, X[n+1][1])) cost = Y[n+1][0] - Y[n][0] # yも同様 adj[Y[n+1][1]].append((cost, Y[n][1])) adj[Y[n][1]].append((cost, Y[n+1][1]))
visited = [0] * N # 訪問フラグ pq = [] # 優先度付きキュー for w, t in adj[0]: # 始点はどこでも良いので、0とする heapq.heappush(pq, (w, t)) visited[0] = 1# 始点の訪問フラグを立てる
ans = 0 while(pq): # 訪問済みならスキップ w, t = heapq.heappop(pq) if visited[t]: continue visited[t] = 1# 訪問フラグを立てる ans += w # スコアに加算 for w, s in adj[t]: # 隣接する頂点を列挙 if visited[s]==0: # 未訪問なら探索候補としてpqに追加 heapq.heappush(pq, (w, s)) print (ans)
import heapq V, E = map(int, input().split()) # 頂点、辺 adj = [ [] for v in range(V)] # 隣接リスト for e in range(E): s, t, w = map(int, input().split()) adj[s].append((t,w)) adj[t].append((s,w))
visited = [0] * V # 訪問フラグ pq = [] # 優先度付きキュー for t, w in adj[0]: # 始点はどこでも良いので、0とする heapq.heappush(pq, (w, t)) visited[0] = 1# 始点の訪問フラグを立てる
ans = 0 while(pq): w, t = heapq.heappop(pq) if visited[t]: # 訪問済みならスキップ continue visited[t] = 1# 訪問フラグを立てる ans += w # スコアに加算 for s, w in adj[t]: # 隣接する頂点を列挙 if visited[s]==0: # 未訪問なら探索候補としてpqに追加 heapq.heappush(pq, (w, s)) print (ans)
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])) # 残っている銀貨の枚数は問わない