Math
Dynamic Programming
Combinatorics
Number Theory
Description
You are given two integers n
and maxValue
, which are used to describe an ideal array.
A 0-indexed integer array arr
of length n
is considered ideal if the following conditions hold:
Every arr[i]
is a value from 1
to maxValue
, for 0 <= i < n
.
Every arr[i]
is divisible by arr[i - 1]
, for 0 < i < n
.
Return the number of distinct ideal arrays of length n
. Since the answer may be very large, return it modulo 109 + 7
.
Example 1:
Input: n = 2, maxValue = 5
Output: 10
Explanation: The following are the possible ideal arrays:
- Arrays starting with the value 1 (5 arrays): [1,1], [1,2], [1,3], [1,4], [1,5]
- Arrays starting with the value 2 (2 arrays): [2,2], [2,4]
- Arrays starting with the value 3 (1 array): [3,3]
- Arrays starting with the value 4 (1 array): [4,4]
- Arrays starting with the value 5 (1 array): [5,5]
There are a total of 5 + 2 + 1 + 1 + 1 = 10 distinct ideal arrays.
Example 2:
Input: n = 5, maxValue = 3
Output: 11
Explanation: The following are the possible ideal arrays:
- Arrays starting with the value 1 (9 arrays):
- With no other distinct values (1 array): [1,1,1,1,1]
- With 2nd distinct value 2 (4 arrays): [1,1,1,1,2], [1,1,1,2,2], [1,1,2,2,2], [1,2,2,2,2]
- With 2nd distinct value 3 (4 arrays): [1,1,1,1,3], [1,1,1,3,3], [1,1,3,3,3], [1,3,3,3,3]
- Arrays starting with the value 2 (1 array): [2,2,2,2,2]
- Arrays starting with the value 3 (1 array): [3,3,3,3,3]
There are a total of 9 + 1 + 1 = 11 distinct ideal arrays.
Constraints:
2 <= n <= 104
1 <= maxValue <= 104
Solutions
Solution 1
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 class Solution :
def idealArrays ( self , n : int , maxValue : int ) -> int :
@cache
def dfs ( i , cnt ):
res = c [ - 1 ][ cnt - 1 ]
if cnt < n :
k = 2
while k * i <= maxValue :
res = ( res + dfs ( k * i , cnt + 1 )) % mod
k += 1
return res
c = [[ 0 ] * 16 for _ in range ( n )]
mod = 10 ** 9 + 7
for i in range ( n ):
for j in range ( min ( 16 , i + 1 )):
c [ i ][ j ] = 1 if j == 0 else ( c [ i - 1 ][ j ] + c [ i - 1 ][ j - 1 ]) % mod
ans = 0
for i in range ( 1 , maxValue + 1 ):
ans = ( ans + dfs ( i , 1 )) % mod
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41 class Solution {
private int [][] f ;
private int [][] c ;
private int n ;
private int m ;
private static final int MOD = ( int ) 1e9 + 7 ;
public int idealArrays ( int n , int maxValue ) {
this . n = n ;
this . m = maxValue ;
this . f = new int [ maxValue + 1 ][ 16 ] ;
for ( int [] row : f ) {
Arrays . fill ( row , - 1 );
}
c = new int [ n ][ 16 ] ;
for ( int i = 0 ; i < n ; ++ i ) {
for ( int j = 0 ; j <= i && j < 16 ; ++ j ) {
c [ i ][ j ] = j == 0 ? 1 : ( c [ i - 1 ][ j ] + c [ i - 1 ][ j - 1 ] ) % MOD ;
}
}
int ans = 0 ;
for ( int i = 1 ; i <= m ; ++ i ) {
ans = ( ans + dfs ( i , 1 )) % MOD ;
}
return ans ;
}
private int dfs ( int i , int cnt ) {
if ( f [ i ][ cnt ] != - 1 ) {
return f [ i ][ cnt ] ;
}
int res = c [ n - 1 ][ cnt - 1 ] ;
if ( cnt < n ) {
for ( int k = 2 ; k * i <= m ; ++ k ) {
res = ( res + dfs ( k * i , cnt + 1 )) % MOD ;
}
}
f [ i ][ cnt ] = res ;
return res ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 class Solution {
public :
int m , n ;
const int mod = 1e9 + 7 ;
vector < vector < int >> f ;
vector < vector < int >> c ;
int idealArrays ( int n , int maxValue ) {
this -> m = maxValue ;
this -> n = n ;
f . assign ( maxValue + 1 , vector < int > ( 16 , -1 ));
c . assign ( n , vector < int > ( 16 , 0 ));
for ( int i = 0 ; i < n ; ++ i )
for ( int j = 0 ; j <= i && j < 16 ; ++ j )
c [ i ][ j ] = ! j ? 1 : ( c [ i - 1 ][ j ] + c [ i - 1 ][ j - 1 ]) % mod ;
int ans = 0 ;
for ( int i = 1 ; i <= m ; ++ i ) ans = ( ans + dfs ( i , 1 )) % mod ;
return ans ;
}
int dfs ( int i , int cnt ) {
if ( f [ i ][ cnt ] != -1 ) return f [ i ][ cnt ];
int res = c [ n - 1 ][ cnt - 1 ];
if ( cnt < n )
for ( int k = 2 ; k * i <= m ; ++ k )
res = ( res + dfs ( k * i , cnt + 1 )) % mod ;
f [ i ][ cnt ] = res ;
return res ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43 func idealArrays ( n int , maxValue int ) int {
mod := int ( 1e9 ) + 7
m := maxValue
c := make ([][] int , n )
f := make ([][] int , m + 1 )
for i := range c {
c [ i ] = make ([] int , 16 )
}
for i := range f {
f [ i ] = make ([] int , 16 )
for j := range f [ i ] {
f [ i ][ j ] = - 1
}
}
var dfs func ( int , int ) int
dfs = func ( i , cnt int ) int {
if f [ i ][ cnt ] != - 1 {
return f [ i ][ cnt ]
}
res := c [ n - 1 ][ cnt - 1 ]
if cnt < n {
for k := 2 ; k * i <= m ; k ++ {
res = ( res + dfs ( k * i , cnt + 1 )) % mod
}
}
f [ i ][ cnt ] = res
return res
}
for i := 0 ; i < n ; i ++ {
for j := 0 ; j <= i && j < 16 ; j ++ {
if j == 0 {
c [ i ][ j ] = 1
} else {
c [ i ][ j ] = ( c [ i - 1 ][ j ] + c [ i - 1 ][ j - 1 ]) % mod
}
}
}
ans := 0
for i := 1 ; i <= m ; i ++ {
ans = ( ans + dfs ( i , 1 )) % mod
}
return ans
}
Solution 2
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 class Solution :
def idealArrays ( self , n : int , maxValue : int ) -> int :
c = [[ 0 ] * 16 for _ in range ( n )]
mod = 10 ** 9 + 7
for i in range ( n ):
for j in range ( min ( 16 , i + 1 )):
c [ i ][ j ] = 1 if j == 0 else ( c [ i - 1 ][ j ] + c [ i - 1 ][ j - 1 ]) % mod
dp = [[ 0 ] * 16 for _ in range ( maxValue + 1 )]
for i in range ( 1 , maxValue + 1 ):
dp [ i ][ 1 ] = 1
for j in range ( 1 , 15 ):
for i in range ( 1 , maxValue + 1 ):
k = 2
while k * i <= maxValue :
dp [ k * i ][ j + 1 ] = ( dp [ k * i ][ j + 1 ] + dp [ i ][ j ]) % mod
k += 1
ans = 0
for i in range ( 1 , maxValue + 1 ):
for j in range ( 1 , 16 ):
ans = ( ans + dp [ i ][ j ] * c [ - 1 ][ j - 1 ]) % mod
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 class Solution {
private static final int MOD = ( int ) 1e9 + 7 ;
public int idealArrays ( int n , int maxValue ) {
int [][] c = new int [ n ][ 16 ] ;
for ( int i = 0 ; i < n ; ++ i ) {
for ( int j = 0 ; j <= i && j < 16 ; ++ j ) {
c [ i ][ j ] = j == 0 ? 1 : ( c [ i - 1 ][ j ] + c [ i - 1 ][ j - 1 ] ) % MOD ;
}
}
long [][] dp = new long [ maxValue + 1 ][ 16 ] ;
for ( int i = 1 ; i <= maxValue ; ++ i ) {
dp [ i ][ 1 ] = 1 ;
}
for ( int j = 1 ; j < 15 ; ++ j ) {
for ( int i = 1 ; i <= maxValue ; ++ i ) {
int k = 2 ;
for (; k * i <= maxValue ; ++ k ) {
dp [ k * i ][ j + 1 ] = ( dp [ k * i ][ j + 1 ] + dp [ i ][ j ] ) % MOD ;
}
}
}
long ans = 0 ;
for ( int i = 1 ; i <= maxValue ; ++ i ) {
for ( int j = 1 ; j < 16 ; ++ j ) {
ans = ( ans + dp [ i ][ j ] * c [ n - 1 ][ j - 1 ] ) % MOD ;
}
}
return ( int ) ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 using ll = long long ;
class Solution {
public :
const int mod = 1e9 + 7 ;
int idealArrays ( int n , int maxValue ) {
vector < vector < int >> c ( n , vector < int > ( 16 ));
for ( int i = 0 ; i < n ; ++ i )
for ( int j = 0 ; j <= i && j < 16 ; ++ j )
c [ i ][ j ] = j == 0 ? 1 : ( c [ i - 1 ][ j ] + c [ i - 1 ][ j - 1 ]) % mod ;
vector < vector < ll >> dp ( maxValue + 1 , vector < ll > ( 16 ));
for ( int i = 1 ; i <= maxValue ; ++ i ) dp [ i ][ 1 ] = 1 ;
for ( int j = 1 ; j < 15 ; ++ j ) {
for ( int i = 1 ; i <= maxValue ; ++ i ) {
int k = 2 ;
for (; k * i <= maxValue ; ++ k ) dp [ k * i ][ j + 1 ] = ( dp [ k * i ][ j + 1 ] + dp [ i ][ j ]) % mod ;
}
}
ll ans = 0 ;
for ( int i = 1 ; i <= maxValue ; ++ i )
for ( int j = 1 ; j < 16 ; ++ j )
ans = ( ans + dp [ i ][ j ] * c [ n - 1 ][ j - 1 ]) % mod ;
return ( int ) ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 func idealArrays ( n int , maxValue int ) int {
mod := int ( 1e9 ) + 7
c := make ([][] int , n )
for i := range c {
c [ i ] = make ([] int , 16 )
}
for i := 0 ; i < n ; i ++ {
for j := 0 ; j <= i && j < 16 ; j ++ {
if j == 0 {
c [ i ][ j ] = 1
} else {
c [ i ][ j ] = ( c [ i - 1 ][ j ] + c [ i - 1 ][ j - 1 ]) % mod
}
}
}
dp := make ([][] int , maxValue + 1 )
for i := range dp {
dp [ i ] = make ([] int , 16 )
dp [ i ][ 1 ] = 1
}
for j := 1 ; j < 15 ; j ++ {
for i := 1 ; i <= maxValue ; i ++ {
k := 2
for ; k * i <= maxValue ; k ++ {
dp [ k * i ][ j + 1 ] = ( dp [ k * i ][ j + 1 ] + dp [ i ][ j ]) % mod
}
}
}
ans := 0
for i := 1 ; i <= maxValue ; i ++ {
for j := 1 ; j < 16 ; j ++ {
ans = ( ans + dp [ i ][ j ] * c [ n - 1 ][ j - 1 ]) % mod
}
}
return ans
}
GitHub