差分
このページの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> |