差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:contest_history:atcoder:2019:0106_educational_dp [2019/01/10] – ikatakos | programming_algorithm:contest_history:atcoder:2019:0106_educational_dp [2019/01/10] – [解法] ikatakos | ||
---|---|---|---|
行 177: | 行 177: | ||
* $K$ 個のキャンディを、余りなく $N$ 人の子供に分ける | * $K$ 個のキャンディを、余りなく $N$ 人の子供に分ける | ||
* 各子供には上限 $a_1, | * 各子供には上限 $a_1, | ||
- | * 配り方のパターン数を、$\MOD 10^9+7$ で求めよ | + | * 配り方のパターン数を、$\mod{10^9+7}$ で求めよ |
* $1 \le N \le 100$ | * $1 \le N \le 100$ | ||
* $1 \le K \le 10^5$ | * $1 \le K \le 10^5$ | ||
行 188: | 行 188: | ||
==データ== | ==データ== | ||
- | $DP[i][j]=i$人目までの子供に、$j$ 個の飴を配るパターン数 | + | $DP[i][j]=i$人目までの子供に、合計 |
として考える。$j$ の範囲は $0~K$ で用意することになる。 | として考える。$j$ の範囲は $0~K$ で用意することになる。 | ||
行 211: | 行 211: | ||
| | ||
- | この各遷移の各 $j$ につき、$DP[i-1]$ の参照と $DP[i]$ への加算が発生するので、$i-1$ から $i$ への遷移で計算が $K \times a_i$ 回発生することになる。それぞれ上限 $10^5$ なので、間に合わない。 | + | この、○個配ったときの各遷移の各 $j$ につき、$DP[i-1]$ の参照と $DP[i]$ への加算が発生するので、$i-1$ から $i$ への遷移で計算が $K \times a_i$ 回発生することになる。それぞれ上限 $10^5$ なので、間に合わない。 |
===圧縮=== | ===圧縮=== | ||
行 248: | 行 248: | ||
上限を設けない場合、配り方のパターン数は、直前の状態(1, | 上限を設けない場合、配り方のパターン数は、直前の状態(1, | ||
- | よって、累積和でまとめてしまえば、1回の遷移にかかる計算を $K$ 回に省略でき、間に合う。 | + | よって、累積和でまとめてしまえば、1回の遷移にかかる計算を上限 |
<sxh python> | <sxh python> |