差分

この文書の現在のバージョンと選択したバージョンの差分を表示します。

この比較画面にリンクする

両方とも前のリビジョン 前のリビジョン
programming_algorithm:contest_history:atcoder:2020:0111_dwacon6th_prelims [2020/01/14]
ikatakos [解法]
programming_algorithm:contest_history:atcoder:2020:0111_dwacon6th_prelims [2020/01/14] (現在)
ikatakos [解法]
ライン 84: ライン 84:
 今までは $k$ を固定して考えていたが、$k=0~i-1$ までの値を取るので、この総和を取ったものが $d_i$ の寄与回数となる。(あくまで $d_i$ より左のみ) 今までは $k$ を固定して考えていたが、$k=0~i-1$ までの値を取るので、この総和を取ったものが $d_i$ の寄与回数となる。(あくまで $d_i$ より左のみ)
  
-$\displaystyle ​\sum_{k=0}^{i-1}\frac{(i-1)!}{k!}(R_k+k!) = (i-1)!\sum_{k=0}^{i-1}\frac{R_k+k!}{k!}$+$\displaystyle (i-1)!\sum_{k=0}^{i-1}\frac{R_k+k!}{k!}$
  
 これをこのまま計算すると各 $i$ の中で $k$ のループが回るので $O(N^2)$ だが、$\sum$ 内は $k$ のみに依存するので、 これをこのまま計算すると各 $i$ の中で $k$ のループが回るので $O(N^2)$ だが、$\sum$ 内は $k$ のみに依存するので、
programming_algorithm/contest_history/atcoder/2020/0111_dwacon6th_prelims.txt · 最終更新: 2020/01/14 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0