3046

1からTまでの数字について、それぞれを使える回数の上限値が与えられるので、A個以上B個以下の数字の集合を作る方法は何通りあるか答えよ、という問題。

単純にDPやるだけ。全部のテーブルを持っていると、メモリが足りなくなるので、直近だけ覚えておくようにする。次に使う数字と、今までに使った個数で何通りかをメモする。ちなみに、K個使える数字のテーブル更新時に0個からK個まで毎回計算すると追い付かないので、それくらいは最適化が必要。