ARC110
A
全部掛けて+1したら余りの条件を満たすけど、大きくなりすぎるので最小公倍数を求めました
関連: 中国剰余定理
pythonfrom math import gcd
N = int(input())
x = 1
for i in range(2, N + 1):
g = gcd(x, i)
x *= i // g
print(x + 1)B
要するにこのオートマトンが受理するかどうか
入力が1文字の時にトラップがあるのでそこだけ場合わけ
pythondef solve(N, T):
if N == 1:
if T == "1":
return 2 * 10 ** 10
elif T == "0":
return 10 ** 10
state = [True, True, True]
for c in T:
nextState = [0] * 3
for i in range(3):
nextState[i] = state[i - 1] and (c == "011"[i])
state = nextState
ret = 0
for i in range(3):
if state[i]:
ret += (3 * 10 ** 10 - ((i - N) % 3 + N)) // 3 + 1
return retRelated Pages
- →chokudai×貪欲法の証明パターン×選択肢が少ない方から貪欲×マトロイド×クラスカル法×区間スケジューリング×交換しても悪化しない×アルゴリズムとデータ構造×区間はマトロイドではない×abc076b×現在が良いほど未来も良い×poj3617×poj3069×ダイクストラ法×agc009a×arc111×abc187×ARC110C×一回り小さい同じ形の問題×agc049b×abc103d×abc023d×和の比率の最大化×単位時間ジョブスケジューリング問題×乱択＋貪欲×abc171_f×離散凸性→
- →二項定理×ホッケースティック恒等式×vandermondeの恒等式×ARC110D×eq6-3をeq6-2に帰着×重複組合せの畳み込み×eq7-proof×二項係数の和とフィボナッチ×数え上げテクニック集→
- →atcoder×atcoder_library_practice_contest×numba×cython×フェニック木×セグメント木×遅延伝搬セグメント木×接尾辞配列×lcp_array×pythonでの累乗・逆数・階乗・階乗逆数・組み合わせ×中国剰余定理×floor_sum×np.convolve×two_snuke×長整数が速い×dsu×unionfind×最大流×最小費用流×scc×2-sat→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]