2019-08-27 ABC132 F - Small Products 動的計画法(DP) 問題 提出コード 解法 番目にを置くような数列の場合の数(ただし、 ) 番目に、を満たすようなを置く数列の場合の数 とします。 以下で最大の整数を、を満たすようなの個数をとすると、それぞれ次のように遷移を行うことができます。 あとは、全てΣの形になっているので、この部分を累積和で高速化することにより、の総和が答えとなります。 初期値は、それ以外がです。