SRM564 Div1 500

問題

赤玉がr個、緑玉がg個、青玉がb個あり、以下のルールを上から順に繰り返す。
・赤玉が残っていれば、赤玉を1つ取り除く
・緑玉が残っていれば、緑玉を1つ取り除く
・青玉が残っていれば、青玉を1つ取り除く

しかし、合計数r+g+b=n個だったこととk回目に赤玉を取り除いたこと以外、忘れてしまった。
(r,g,b)の組み合わせとして何種類あり得るか。

1<=n<=10^5
1<=k<=n

考え方

dp。

単純に、dp[]=組み合わせの総数と考えると、
iの状態からi+1の状態を計算するには、
・何回目か
・r,g,bの残り個数
・何を最後に使ったか
が考えられる。
「r,g,bの残り個数」は、区別せずに「r,g,bが残っているか否か」でもよい。
なので、
dp[何回目か][r,g,bの残っているか否かのフラグ(8通り)][最後に何を使ったか(3色)]=組み合わせ総数
になる。

更新は、各状態において、
「単純に個数が減るだけのパターン」「その色が使ってなくなるパターン」に現在の状態を配る。
ただし、k回目の場合は、赤玉だけ更新する必要がある。