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