差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:contest_history:atcoder:2020:0111_dwacon6th_prelims [2020/01/12] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2020:0111_dwacon6th_prelims [2020/01/12] – [解法] ikatakos | ||
|---|---|---|---|
| 行 95: | 行 95: | ||
| ===まとめ=== | ===まとめ=== | ||
| - | $R_0=0$ として、$\displaystyle dp(i)=\sum_{k=0}^{i}\frac{R_k+k!}{k!}$、つまり $dp(0)=1$ とする。 | + | $R_0=0$ として、$\displaystyle dp[i]=\sum_{k=0}^{i}\frac{R_k+k!}{k!}$、つまり $dp[0]=1$ とする。 |
| 左の区間から、通過総数を計算していく。 | 左の区間から、通過総数を計算していく。 | ||
| - | 区間 $d_i$ の答えへの加算は、$d_i \times (i-1)! dp(i-1) \times \frac{N!}{i!}$ となる。 | + | 区間 $d_i$ の答えへの加算は、$d_i \times (i-1)! dp[i-1] \times \frac{N!}{i!}$ となる。 |
| - | $dp(i)=dp(i-1)+\frac{(i-1)! dp(i-1) + i!}{i!}$ として次の区間の計算に備える。 | + | $dp[i]=dp[i-1]+\frac{(i-1)! dp[i-1] + i!}{i!}$ として次の区間の計算に備える。 |
| <sxh python> | <sxh python> | ||
