Count the number of ideal arrays

Math Dynamic Programming Combinatorics Number Theory

56.9% acceptance

Feb 25, 2026

844

133

A 0-indexed integer array arr of length n is ideal if: Every arr[i] is a value from 1 to maxValue. Every arr[i] is divisible by arr[i-1]. Return the number of distinct ideal arrays of length n modulo 10^9+7.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn ideal_arrays(n: i32, max_value: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = n as usize;
    let max_val = max_value as usize;
    let max_len = 14usize; // max chain length: log2(10000) < 14

    // dp[v][k] = number of strictly increasing divisibility chains of length k ending at v
    let mut dp = vec![vec![0i64; max_len + 1]; max_val + 1];
    for v in 1..=max_val {
      dp[v][1] = 1;
    }
    // For each v, propagate to its multiples
    for v in 1..=max_val {
      let mut mul = v * 2;
      while mul <= max_val {
        for k in 1..max_len {
          if dp[v][k] > 0 {
            dp[mul][k + 1] = (dp[mul][k + 1] + dp[v][k]) % MOD;
          }
        }
        mul += v;
      }
    }

    // Precompute C(n-1, k-1) for k = 1..max_len using modular arithmetic
    fn pow_mod(mut base: i64, mut exp: i64, modulus: i64) -> i64 {
      let mut result = 1i64;
      base %= modulus;
      while exp > 0 {
        if exp % 2 == 1 { result = result * base % modulus; }
        exp /= 2;
        base = base * base % modulus;
      }
      result
    }

    let m = (n - 1) as i64;
    let mut comb = vec![0i64; max_len + 1];
    comb[0] = 1;
    for j in 1..=max_len {
      if m < j as i64 {
        comb[j] = 0;
      } else {
        comb[j] = comb[j - 1] * ((m - j as i64 + 1) % MOD) % MOD
          * pow_mod(j as i64, MOD - 2, MOD) % MOD;
      }
    }

    let mut ans: i64 = 0;
    for v in 1..=max_val {
      for k in 1..=max_len {
        if dp[v][k] > 0 {
          ans = (ans + dp[v][k] * comb[k - 1]) % MOD;
        }
      }
    }
    ans as i32
  }
}