差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン 前のリビジョン | |||
|
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 | + | $\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$ のみに依存するので、 | ||
