LeetCode. 6115 count the number of ideal arrays

Topic link

---

Title Description

Here are two integers n and maxValue , Used to describe a Ideal array .

For subscripts from 0 Start 、 The length is n Array of integers for arr , If the following conditions are met , The array is considered to be a Ideal array ：

• Every arr[i] from 1 To maxValue A value in the range , among 0 <= i < n .
• Every arr[i] Can be arr[i - 1] to be divisible by , among 0 < i < n .

Return length is n Of Different Number of ideal arrays . Because the answer can be big , Return to right $10^9+7$ The result of taking the remainder .

---

Example 1：

 Input ：n = 2, maxValue = 5
 Output ：10
 explain ： There are the following ideal arrays ：
-  With  1  The first array （5  individual ）：[1,1]、[1,2]、[1,3]、[1,4]、[1,5]
-  With  2  The first array （2  individual ）：[2,2]、[2,4]
-  With  3  The first array （1  individual ）：[3,3]
-  With  4  The first array （1  individual ）：[4,4]
-  With  5  The first array （1  individual ）：[5,5]
 total  5 + 2 + 1 + 1 + 1 = 10  Different ideal arrays .

---

Example 2：

 Input ：n = 5, maxValue = 3
 Output ：11
 explain ： There are the following ideal arrays ：
-  With  1  The first array （9  individual ）：
   -  Other different values are not included （1  individual ）：[1,1,1,1,1] 
   -  Contains a different value  2（4  individual ）：[1,1,1,1,2], [1,1,1,2,2], [1,1,2,2,2], [1,2,2,2,2]
   -  Contains a different value  3（4  individual ）：[1,1,1,1,3], [1,1,1,3,3], [1,1,3,3,3], [1,3,3,3,3]
-  With  2  The first array （1  individual ）：[2,2,2,2,2]
-  With  3  The first array （1  individual ）：[3,3,3,3,3]
 total  9 + 1 + 1 = 11  Different ideal arrays .

---

Tips ：

• $2<=n<=10^4$
• $1<=maxValue<=10^4$

---

Answer key

---

Algorithm 1: dp

dp[ i][ j] by : front i Elements , The last element is j; Every time I traverse his divisor

The time complexity is : O(n * m * sqrt(m)), Overtime

---

Algorithm 2: Optimize dp

dp[ i][ j] by : front i Elements , The last element is : all j The divisor of , Every time with the current dp To update dp[ i][ j Multiple ]

Time is : O( n * m * log( m)), 1e8 * 15 Also timeout ! Don't take chances .

---

Algorithm 3: Combinatorial mathematics

When it comes to Multiple when , Think of it , This is a Index Magnitude , The increasing speed is very fast !

The maximum is 1e4, Most are 15 Multiple operation 1, 2, 4, 8, 16, 32, ...

therefore , Although this array will be very long , But it's unique After the operation , Most are 15 A different number

With 12 Look at , Its unique after , May be [1, 2, 4, 12], [1, 3, 6, 12], [4, 12], [12], …

Look at it every time Product factor :

• such as [1, 2, 4, 12], His Product factor yes : [2, 2, 3]
• such as [1, 3, 12], His Product factor yes : [3, 4]

Its Product factor Product of , be equal to 12

There is a special [4, 12], The product factor is : [3];
But if you add his first item , namely [4, 3], The product is also 12

---

Define a sequence A Of Product factor B by :

• B[ 1] = A[ 1]
• B[ i] = A[ i] / A[ i - 1], i > 1

Be similar to Difference array .

---

For a length of n, And the last element is m Of Ideal array A, The product factor is B Array , Then there are :

• $ \prod{B} = m $
• B[ i] = 1 or m The divisor of

A: [1, 2, 2, 4, 12] -> B: [1, 2, 1, 2, 3]
A: [4, 4, 4, 4, 12] -> B: [4, 1, 1, 1, 3]
A: [12, 12, 12, 12, 12] -> B: [12, 1, 1, 1, 1]

The question turned to : stay B Array of n In one position , discharge m Of Not 1 The divisor of , Put all other positions 1 Number of alternatives .

Because of a number of Divisor , There are many . Divisors can be decomposed into prime factors , And few qualitative factors , From the perspective of qualitative factors

12 The quality factor of = 2, 2, 3

---

The problem at this point is : Will this 3 A quality factor , Put in B the n In one position ; Put >=0 individual . namely Ball and box model

• this n A place , namely The box , yes Different The box ; such as [ empty , 2] and [2, empty ] Is different

• And these qualitative factors ? All are Same ball ? still Different balls ?
  such as : [2, 3] and [3, 2] Is different , therefore : Different qualitative factors , It's a different ball
  however : [2, 2] and [2, 2] It's the same , namely : Same qualitative factor , It's the same ball

That is to say , about The same quality factor , They are Same ball , It should be converted to : Same ball Of Ball and box model

that , Can different qualitative factors be separated ? Split into several sub problems , Each sub problem is ** Same ball Of Ball and box model **

because Different qualitative factors can be put into The same In the box , therefore , Different qualitative factors Can be handled separately .
The scheme of each different qualitative factor , adopt Reunite with , In order to gain The solution of the original problem . there Reunite with , Is to meet Multiplication principle Of

If different balls cannot be put The same The box , Cannot be split ; otherwise :
such as , If you split [2, empty ] and [3, empty ]; They compounded into [23, empty ], The program is illegal .

For the sub problem after splitting : a Same ball , elect a individual , Put it in b In a different box , And each box >=0 individual
This is a Empty partition method , namely : $C_{a+b-1}^{b-1}$

a = 15, b = 1e4, That is, the range of all combinations is : C[ 1e4][ 1e4]
It seems impossible to preprocess , however : because a Very small , b It's big , Application The equivalence of combinatorial numbers
C[ a + b - 1][ b - 1] == C[ a + b - 1][ a]
That is, it turns into : C[ 1e4][ 15] The magnitude of !!! Can be preprocessed

---

Code

#define GET_( _t, _i) ::std::get< _i>( _t)
#define FOR_( _i, _l, _r, _s) for( int _i = _l; _i <= _r; _i += _s)
#define FOR_RE_( _i, _l, _r, _s) for( int _i = _l; _i >= _r; _i -= _s)

class Solution {
    
public:
    int P[ 100], P_size;
    int C[ 10055][ 15]; //< 2^14 > 1e4
    static constexpr int Mod_ = 1e9 + 7;
    void init_C(){
    
        C[ 0][ 0] = 0;
        FOR_( i, 1, 10050, 1){
    
            C[ i][ 0] = 1;
            if( i <= 14){
    
                C[ i][ i] = 1;
            }
            FOR_( j, 1, min( i - 1, 14), 1){
    
                C[ i][ j] = (C[ i - 1][ j] + C[ i - 1][ j - 1]) % Mod_;
            }
        }
    }
    int get_C( int _a, int _b){
    
        assert( _a >= _b);
        if( ( _a - _b) < _b){
    
            _b = _a - _b;
        }
        //*  Or inverse element ( C = a / b),  Or pretreatment (C = a + b)
        //*  If you want to ask directly ,  Although his result is an integer ,  namely (C = a / b), b It can definitely be eliminated ,  but a It's big ,  Explosive ll
        return C[ _a][ _b];
    }
    int idealArrays(int _n, int _ma) {
    
        init_C();
        long long ans = 0;
        ans ++; //< [1, ..., 1]
        FOR_( i, 2, _ma, 1){
     //< 1 Special treatment ,  because 1 Cannot prime factorize 
            P_size = 0;
            int temp = i;
            for( int j = 2; j <= temp / j; ++j){
    
                if( temp % j == 0){
    
                    P[ P_size] = 0;
                    while( temp % j == 0){
    
                        ++ P[ P_size];
                        temp /= j;
                    }
                    ++ P_size;
                }
            }
            if( temp > 1){
    
                P[ P_size] = 1;
                ++ P_size;
            }
            //--
            long long anss = 1;
            FOR_( j, 0, P_size - 1, 1){
    
                anss *= get_C( _n + P[ j] - 1, _n - 1);
                anss %= Mod_;
            }
            ans += anss;
            ans %= Mod_;
        }
        return ans;
    }
};