差分
このページの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$ のみに依存するので、 | ||
