phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

ABC132 F. Small Products

問題

正の整数K個を一列に並べたもので、隣接するどの2つの整数の積もN以下であるようなものの個数を求めよ。
答えは10^9+7のあまりで求めよ。

制約

  • 1 <= N <= 10^9
  • 2 <= K <= 100

解放

計算量を無視して考えると、
dp[i][j] := i番目の整数がjだった場合の通り数
のように考えられる。
この遷移は、dp[i][j] = Σ_{1<=k<=N/j} dp[i-1][k]のようにして求めていける。

この計算量を減らすことを考える。
i番目が整数jと考えているときに、遷移のΣの「1<=k<=N/j」は、累積和を求めておけばO(1)で求められるので、O(K*N)になる。
さらに、この「N/j」に注目すると、例えばN=100に対し、j=98とj=99はどちらもN/jは1となっていることがわかる。
このように、N/jが同じになるjは遷移の右辺が同じになるので、まとめて計算することを考える。

N/jとしてありえる値は、j=1~√Nまでに対して、jとN/jを実際に出してみて、出てくる整数を考えれば良い。(setなどに入れておく)
この整数以外の、抜けてる整数は、個数がわかるので、出てくる整数のところにまとめて数え上げればよい。
したがって、全体でO(K*√N)程度で求められる。