差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:contest_history:atcoder:2020:0110_abc150 [2020/01/12] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2020:0110_abc150 [2020/01/12] – ikatakos | ||
|---|---|---|---|
| 行 2: | 行 2: | ||
| [[https:// | [[https:// | ||
| + | |||
| + | * 解説放送: | ||
| ===== D - Semi Common Multiple ===== | ===== D - Semi Common Multiple ===== | ||
| 行 115: | 行 117: | ||
| しかし、このままでは1つの $i$ を求める内部でさらに $\sum$ のループがあるため $O(N^2)$ となってしまう。 | しかし、このままでは1つの $i$ を求める内部でさらに $\sum$ のループがあるため $O(N^2)$ となってしまう。 | ||
| - | ここで、二項係数の総和の公式より、$\displaystyle \sum_{r=0}^{n}{{}_nC_r | + | ここで、二項係数の総和の公式より、$\displaystyle \sum_{r=0}^{n}{{}_nC_r(r+1)}=2^{n-1}(n+2)$ となることを利用できる。 |
| * [[https:// | * [[https:// | ||
