AtCoder ABC #132 F - Small Products

AtCoder AtCoder ABC ABC#132 DP AtCoder 600点 累積和

F - Small Products

問題

正の整数K個を一列に並べたものであって、隣接して並んでいるどの2つの整数の積もN以下であるものの個数を109+7で割った余りを求めてください。

解説

公式解説にあるようにxが最後の整数となるようなi個の整数を並べて条件を満たす場合の数dp[i][x]を使ったプログラムをまず書いてみる。

const MOD: i64 = 1000000000 + 7;

fn solve(n: usize, k: usize) -> i64 {
    let mut dp = vec![vec![0i64; n + 1]; k + 1];

    for i in 1..(n + 1) {
        dp[1][i] = i as i64;
    }

    for i in 2..(k + 1) {
        for j in 1..(n + 1) {
            dp[i][j] = (dp[i - 1][n / j] + dp[i][j - 1]) % MOD;
        }
    }

    dp[k][n]
}

累積和を使ってることに注意。ただし、もちろんこいつはLTEとなる。

次に公式解説に従って O(NK)が O(\sqrt{N}K)となるように改良する。

例えば N=25の場合商が同じになる方の組み合わせは以下のようになる。

レイヤ 法 商
1 1 25
2 2 12
3 3 8
4 4 6
5 5 5
6 7,8 3
7 9,..,12 2
8 13,..,25 1

DPをレイヤごとに構築してやると O(\sqrt{N}K)が達成される。

const MOD: i64 = 1e9 as i64 + 7;

fn solve(n: usize, k: usize) -> i64 {
    let sqn = (n as f64).sqrt() as usize;
    let q = n / (sqn + 1);
    let r = sqn + q;

    let mut dp = vec![vec![0i64; 2 * r]; k + 1];

    let mut num = vec![0; r + 1];
    for i in 1..(r + 1) {
        if i <= sqn {
            num[i] = 1;
            dp[1][i] = dp[1][i - 1] + 1;
        } else {
            num[i] = (n / (r - i + 1) - n / (r - i + 2)) as i64;
            dp[1][i] = dp[1][i - 1] + num[i];
        }
    }

    for i in 2..(k + 1) {
        for j in 1..(r + 1) {
            dp[i][j] = (dp[i - 1][r - j + 1] * num[j] + dp[i][j - 1]) % MOD;
        }
    }

    dp[k][r]
}