差分
この文書の現在のバージョンと選択したバージョンの差分を表示します。
| 両方とも前のリビジョン 前のリビジョン | |||
|
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$ のみに依存するので、 | ||
