問題概要

正の整数 $ K (\leq 100)$ 個からなる数列で，隣接するどの 2 つの整数の積も $ N (\leq 10^9)$ 以下であるものの個数を $ {10}^9 + 7 $ で割ったあまりを求めよ．

解法概要

数列の値を左から順に決めるとすると，$ i$ 番目の値を決めるのに必要なのは $ (i-1) $ 番目の値のみである．このことから，(制約をとりあえず置いておくと) 次のような DP が考えられる．

$\mathit{dp}_{i, j} = i$ 番目の値が $ j$ であるような数列の個数 (を$ {10}^9 + 7 $ で割ったあまり)

このとき，更新は次のようにできるはずである．

$ \mathit{dp}_{i, j} = \sum_{k=1}^{t} \mathit{dp}_{i-1, k} $ (ただし $ t = \lfloor \frac{N}{j} \rfloor $)

今回の制約では，この DP は当然間に合わない．(この TLE 解の時間計算量って $ O(N^2K)$ でしょうか？自信がないので教えていただけたら嬉しいです)

累積和を使って，

$ \mathit{dp}_{i, j} = i$ 番目の値が $ j $ 以下であるような数列の個数 (を$ {10}^9 + 7 $ で割ったあまり)

とすると，各更新が定数時間で済むようになり時間計算量が $ O(NK)$ となるが，それでも遅い．

……と，ここまでは自力で考えついてあとは隣り合った要素の積の列などを考えたりもしたが思いつかず，解説をチラ見．

実はこの DP による解法は，状態をまとめることでさらなる時間計算量改善が可能．具体的には，$ \lfloor \frac{N}{j_1} \rfloor = \lfloor \frac{N}{j_2} \rfloor $ となるような $ j_1, j_2 $ はまとめることができる．何故ならば，両者とも

$ \mathit{dp}_{i, j} = i$ 番目の値が $ j$ であるような数列の個数 (を$ {10}^9 + 7 $ で割ったあまり)

について，

$ \mathit{dp}_{i, j_1} = \mathit{dp}_{i, j_2} = \sum_{k=1}^{t} \mathit{dp}_{i-1, k} $ (ただし $ t = \lfloor \frac{N}{j_1} \rfloor = \lfloor \frac{N}{j_2} \rfloor $)

という同一の更新式によって更新できるためである．

そこで $ N$ で割った商が同じ数は同じグループと考えて，グループごとに DP の値を保持して更新もグループごとに行うことで，今まで $ O(NK)$ だった空間計算量が $ O(\sqrt{N}K)$ となる．

時間計算量については，解説によると $ O(\sqrt{N}K)$ で書けるらしい．私の解法だと sort を使っているので $ O(\sqrt{N}\log{N} \cdot K)$ ．

ソースコード

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

using ll =  long long;

constexpr ll MOD = 1000000007;

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> quotients(1, 0);
    for(int i=1;i<=min(n, int(sqrt(n))+1);++i) {
        quotients.push_back(n/i);
        quotients.push_back(n/(n/i));
    }
    sort(quotients.begin(), quotients.end());
    quotients.erase(unique(quotients.begin(), quotients.end()), quotients.end());
    int m = quotients.size();

    vector<int> inv_quotients_idx(m, -1);
    {   
        int j = m-1;
        for(int i=1;i<m;++i) {
            while(i <= j && quotients[i]*quotients[j] > n) --j;
            if(i > j) break;
            inv_quotients_idx[i] = j;
            inv_quotients_idx[j] = i;
        }
    }
    
    vector<vector<ll>> dp(k+1, vector<ll>(m, 0));
    for(int j=1;j<m;++j) dp[0][j] = quotients[j];
    for(int i=1;i<k;++i) {
        for(int j=1;j<m;++j) {
            dp[i][j] = (dp[i-1][inv_quotients_idx[j]] * (quotients[j] - quotients[j-1])) % MOD;
        }

        for(int j=1;j<m;++j) {
            dp[i][j] += dp[i][j-1];
            dp[i][j] %= MOD;
        }
    }

    cout << dp[k-1][m-1] << endl;
    
}

所感

「状態をまとめる」ことを考える際の着眼点や，「本当にまとめて良いのか？」を判断するときに考慮すべきポイントみたいなものを学べた．そういえば DEGwer さんの数え上げ pdf にも状態をまとめられる条件が書いてあったね．

NoiminのNoise

AtCoder Beginner Contest 132 F - Small Products

問題概要

解法概要

ソースコード

所感