差分
このページの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 | ||
|---|---|---|---|
| 行 78: | 行 78: | ||
| $\displaystyle \sum_{k=0}^{i-1}\frac{(i-1)!}{k!}(R_k+k!)$ | $\displaystyle \sum_{k=0}^{i-1}\frac{(i-1)!}{k!}(R_k+k!)$ | ||
| - | これは、$k=0$ から、新しい $R_i$ が求められるたびに $\frac{R_i+i!}{i!}$ を加算していけば、毎回 $\sum$ のループを回さなくても計算できる。 | + | これは、新しい $R_i$ が求められるたびに $\displaystyle |
| ===区間より右のスライム=== | ===区間より右のスライム=== | ||
| 行 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 = 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{D_i + i!}{i!}$ として次の区間の計算に備える。 | + | $dp[i]=dp[i-1]+\frac{(i-1)! dp[i-1] |
| <sxh python> | <sxh python> | ||
