ABC243G Sqrt
自力AC
解をとします。
まず、以下の最大の整数は二分探索により、で得られます。ここでは、とします。
くらいの場合
が与えられた時に生成可能な数列の種類数
と定義すると、
と求められます。
ここで、の累積和をとっておけば、
と求められるので、の計算も含め、小さい方からDPテーブルをで計算できます。
なお、数列の項が1になった時点で1が延々と続くだけなので、初期値はです。
この時の解は、です。
くらいの場合
となります。
前述した通り、までのDPテーブルは計算できるので、解を得られます。
の場合
であり、
であるので、
とおけます。
これより、がとなる個数をとし、とすると、
とできます。
は以下でがとなるものの数です。
は、を満たすの個数として求められます。
とすれば、でDPテーブルを計算できます。
また、をの累積和とすると、
とおけます。
後は、の求め方ですが、
で求められます。