ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC132 F - Small Products

問題
提出コード

解法

dp1[i][j] = i番目にjを置くような数列の場合の数(ただし、j \leqq \sqrt{N} )
dp2[i][j] = i番目に、xj \leqq N \lt x(j+1)を満たすようなx( x \gt \sqrt{N})を置く数列の場合の数
とします。
\sqrt{N}以下で最大の整数をpxj \leqq N \lt  x(j+1)を満たすようなx( x \gt \sqrt{N})の個数をc_{j}とすると、それぞれ次のように遷移を行うことができます。
\displaystyle dp1[i + 1][j] = \sum_{s = 1}^{p} dp1[i][s] + \sum_{m = j}^{p}dp2[i][m]
\displaystyle dp2[i+1][j] = \sum_{s = 1}^{j}dp1[i][s] \times c_{j}


あとは、全てΣの形になっているので、この部分を累積和で高速化することにより、dp1[k][j],dp[k][j]の総和が答えとなります。
初期値はdp1[0][1] = 1、それ以外が0です。