Count the Number of Ideal Arrays

Problem Description

Given two integers n and maxValue, count the number of distinct “ideal” arrays of length n such that:

1. Every element is between 1 and maxValue.
2. For every i > 0, arr[i] % arr[i-1] == 0.

Return the count modulo 10⁹+7.

Key Insights

• Any ideal array can be seen as choosing a strictly increasing divisibility‐chain of distinct values
  [v₁∣v₂∣…∣vₖ], then “spreading” those k values (with repetitions) across the n slots.
• We first count, for each end‑value v and chain‑length k, the number of divisor‑chains ending at v of length k.
• Once a chain of length k is chosen, the number of ways to intersperse its k blocks into the n positions is
  (\displaystyle \binom{n-1}{k-1}).
• The maximum distinct‑value chain‑length is only about (\lfloor\log₂(\text{maxValue})\rfloor+1), so both DP and combinatorics stay efficient.

Space and Time Complexity

• Time:
  • DP “sieve” over v=1…maxValue, extending each chain to its multiples takes
    (\sum_{v=1}^{\text{maxValue}}(\tfrac{\text{maxValue}}{v}\cdot L)=O(\text{maxValue}·\log\text{maxValue}·L)).
  • Precomputing combinations (\binom{s}{k}) for s=0…n-1, k=0…L-1 is (O(n·L)).
  • Final sum is (O(\text{maxValue}·L)).
• Space:
  • cnt[maxValue+1][L] for DP, and comb[n][L] for binomials → (O(\text{maxValue}·L + n·L)).

Solution

1. DP‑build chains
   Let cnt[v][k] = number of strictly‑increasing divisor‑chains of length k+1 that end at v.
   • Initialize cnt[v][0]=1 (the chain [v]).
   • For each v and each k<L-1, add cnt[v][k] into cnt[m][k+1] for every multiple m=v*2, v*3,…≤maxValue.
2. Precompute binomials
   Build Pascal’s triangle comb[s][k] = C(s, k) for 0≤s<n, 0≤k<L.
3. Aggregate answer
   [ \sum_{v=1}^{\text{maxValue}};\sum_{k=0}^{\min(L-1,n-1)} \text{cnt}[v][k];\times;\binom{n-1}{k} ;\bmod 10^{9}+7. ]

Code Solutions