https://atcoder.jp/contests/dp/submissions/10545854
子供たちが飴を分け合うと言うと重複組み合わせっぽく見えるが、重複組み合わせだとDPが書きづらいので子供i-1から子供iに遷移するとき飴jがどうなるかというDPで実装する。このとき、K個の飴を配るというより逆転の発想で残りの飴がj個と考えて子供iが0からA[i]個の飴を取ると考えると実装が楽になる。
- 初期値は rep(i, K-a[0], K) dp[0][i] = 1;
- 繰り返しは rep(i, 1, N) rep(j, 0, K+1)
- 状態は特に無し
- 漸化式は dp[i][j] = dp[i-1][j] + dp[i-1][j+1] + dp[i-1][j+2] + ... + dp[i-1][j+A[i]];
- 最終目標は dp[N][0]
vector<DS_BinaryIndexedTree<mll>> bitdp(N + 1, DS_BinaryIndexedTree<mll>(K + 1));
点加算と区間取得が出来れば良い。自作の遅延セグ木では定数倍が大きすぎてTLEしてしまったので、BIT(Binary Indexed Tree)を使った。[j]の部分をBIT1本で表現し、BITを最大100本用意すれば解くことが出来る。
- 重複組み合わせでなく、遷移を意識する
- 逆転の発想で残りの飴がj個
- 子供iが0からA[i]個の飴を取る遷移(矢印)を意識する
- 最終目標を想像する、子供Nが残りの飴0、dp[N][0]
- dp[i][0からK]の0からKは1本のBITで表現できる
