累積和しながらDP
DPなどの最中に累積和の動的生成することがある
pythondef accum_generation(N):
"""
>>> accum_generation(10)
[1, 0, 1, 1, 1, 2, 2, 3, 4, 5]
"""
value = [0] * (N + 10)
accum = [0] * (N + 10)
value[0] = 1
accum[0] = 1
for pos in range(1, N):
ret = (accum[pos - 2] - accum[pos - 4])
value[pos] = ret
accum[pos] = accum[pos - 1] + ret
return value[:N]Related Pages
- →#×共同化×s-pdca×納得感のない計画×##×双対セグメント木×時間がない×🤖2023-08-12_02:30×ABC179×依頼を先延ばしにする症例×ppoi×agc032b×hatena2009-04-26×「ボードゲームとしてのクリーンランゲージ」とは×hatena2009-05-14×初つぶやきglsl→
- →数え上げ×degwer×状態をまとめる×dpは全探索の高速化×arc059f×codefestival_2016_final_f×aoj2439×探索順の変更×大きい順に並べる×aoj2333×順列は挿入dp×bit_dp×区間は終点でソート×条件の言い換え×操作は多いが産物は少ない×agc013d×線形和への分解×演算順序の変更×ビット演算を桁ごとに分解×部分群×操作が可逆で全域→部分群×ラグランジュの定理×再帰的定義→dp×arc037d×桁DP×aoj0570×累積和×フェニック木×高速フーリエ変換×ntt×高速ゼータ変換×and_と_add_の畳み込み×二分累乗×agc013e×行列木定理×全域木の個数×lgv公式×非交叉経路の個数×小さい確率を無視する×二項係数の公式×経路数×45度回転×xとyにわける×カタラン数×包除原理×agc005d×約数系包除×arc064f→
- →past5h×abc184e×past4j×past4k×abc175d×arc106×abc164d×素因数分解を_o(n^(1/4))_でする×abc189×abc190e×abc194f×atcoderのpythonでmemoryerrorを出すとreになる×agc048×ABC179D×深さ優先探索×aoj_grl_5_c×arc107×agc044a×past2n×past3o×頂点を塗るのか辺を塗るのか×past4m×abc178f×abc192×abc191→
- →僕のatcoderの学び方(〜緑)×僕のatcoderの学び方(〜青)×arc106×気づきの言語化×結晶化×変形テクニックに名前をつける×行列の半分×二項定理×足し算の順序の変更×概念のハンドル×テストできるスニペットライブラリ×unionfind×mod_pでの組み合わせ×Educational DP Contest×動的計画法×atcoder_library_practice_contest×atcoder_library×帰着する力×帰着訓練→
"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]