ABC132 F問題：Small Products

問題. Small Products

正整数からなる長さ の数列で，隣り合うどの 2 要素の積も 以下となるものが何通りあるか求めよ．

制約： ，　

解法．動的計画法 + 累積和

まず，数列の各要素は 1 以上 以下であることが分かる．そこで，dp[i][j] を長さ で末尾の要素が となる条件を満たす数列の数として動的計画法をしたくなるが 時間かかるので高速化が必要である．
ここで，隣り合う2要素の遷移を考えたとき下の図のようにブロックに分割することができる（2つのブロック内のどの要素との積も 以下のときブロック間を矢印で結んでいる）．同じブロック内なら遷移先は同じとなるので状態数を減らすことができる．このブロック数は に関して単調増加となり， のとき 個のブロックに分割することができるので，上の動的計画法を 時間に高速化できた（ はブロック数で ）．また，遷移は連続するブロックとなるので各 の遷移の前で累積和を求めることによって 時間で求めることができる．
　　　　　　　

計算時間：

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(8) << setiosflags(ios::fixed);

    constexpr ll MOD = 1e9 + 7;

    ll n, k;
    cin >> n >> k;

    vector<pair<ll, ll>> b;
    ll ub = n;
    while (0 < ub) {
        ll id = n / ub, lb = max(1ll, (n + 1 + id) / (id + 1));
        b.emplace_back(lb, ub);
        ub = lb - 1;
    }
    reverse(b.begin(), b.end());

    const ll size = b.size();
    vector<int> idx(size);
    for (int i = 0; i < size; ++i) {
        ll ub = n / b[i].second, id = n / ub, lb = (n + 1 + id) / (id + 1);
        pair<ll, ll> key(lb, ub);
        auto it = lower_bound(b.begin(), b.end(), key);
        idx[i] = distance(b.begin(), it);
    }

    vector<vector<ll>> dp(k, vector<ll>(size + 1));
    for (int i = 0; i < size; ++i) dp[0][i] = b[i].second - b[i].first  +1;
    for (int i = 1; i < size; ++i) (dp[0][i] += dp[0][i - 1]) %= MOD;

    for (int i = 1; i < k; ++i) {
        for (int j = 0; j < size; ++j) (dp[i][j] += dp[i - 1][idx[j]]) %= MOD;
        for (int j = 0; j < size; ++j) (dp[i][j] *= (b[j].second - b[j].first + 1)) %= MOD;
        for (int j = 1; j < size; ++j) (dp[i][j] += dp[i][j - 1]) %= MOD;
    }

    cout << dp[k - 1][size - 1] << endl;

    return 0;
}

本番で解けなかったけど後で自力で解けたので嬉しい．バグらせずに細かい部分を速く実装するのが課題．あとで のサイズを考えてみる．

追記．
解説 によると らしい．下図の横軸は で，縦軸が の値．縦軸の値の種類数が に対応．床関数で潰れて が に比べて少ないのが分かる（証明は解説が分かりやすい）．