# 22.04.2025 [2338. Count the Number of Ideal Arrays]
Arrays a[i] % a[i - 1] == 0, i..n, a[i]..max #hard #combinatorics
22.04.2025
2338. Count the Number of Ideal Arrays hard blog post substack youtube
Join me on Telegram
Problem TLDR
Arrays a[i] % a[i - 1] == 0, i..n, a[i]..max #hard #combinatorics
Intuition
Didn't solve. And didn't understand the solution. To make it work you have to be fluent with combinatorics. You have to be fluent with
Stars and barshttps://cp-algorithms.com/combinatorics/stars_and_bars.html.My thoughts rundown is irrelevant here, so I will not post it.
Some thoughts about the solution:
arrays are
aaa | bbb | ccc, where|is the bars.1 | 2 | 4 4or1 1| 2 |4or1 | 2 2 | 4.the max uniq sequence length is for
2:1,2,4,8,2^4,2^5,...2^i,..10000, max i is 2^13=8192 < 10000res +=
n choose k, n in1..maxValue, k in0..13. We considering placing1..maxValuenumbers into a length of0..13places
Approach
maybe I should try more combinatorics problems to better understand them; right now they are not picturing in my brain canvas
Complexity
Time complexity: O(nlog(n))
Space complexity: O(nlog(n))
Code
fun idealArrays(n: Int, maxValue: Int): Int {
val comb = Array(10001) { IntArray(14) }; val cnt = Array(10001) { IntArray(14) }
val M = 1_000_000_007; comb[0][0] = 1; var res = 0L
for (s in 1..10000) { comb[s][0] = 1
for (r in 1..13) comb[s][r] = (comb[s - 1][r - 1] + comb[s - 1][r]) % M }
for (div in 1..10000) {
++cnt[div][0]
for (i in 2 * div..10000 step div) {
var bars = 0
while (cnt[div][bars] > 0) cnt[i][bars + 1] += cnt[div][bars++]
}
}
for (i in 1..maxValue) for (bars in 0..min(13, n))
res = (1L * cnt[i][bars] * comb[n - 1][bars] + res) % M
return res.toInt()
}