Yyds dry goods inventory solution sword finger offer: cut rope (advanced version)

1. sketch ：

describe

I'll give you a length of n The rope of , Please cut the rope to the whole length m paragraph （ m 、 n Are integers. , n > 1 also m > 1 , m <= n ）, The length of each rope is recorded as k[1],...,k[m] . Excuse me, k[1]*k[2]*...*k[m] What's the maximum possible product ？ for example , When the length of the rope is 8 when , We cut it into lengths of 2、3、3 Three paragraphs of , The maximum product we get here is 18 .

Because the answer is too big , Yes, please. 998244353 modulus .

Data range ： Advanced ： Spatial complexity   , Time complexity  

Example 1

Input ：

Log in and copy

      
      

       
       4
      
      
      
      

       
       
1.
      
      

Return value ：

Log in and copy

      
      

       
       4
      
      
      
      

       
       
1.
      
      

explain ：

Log in and copy

      
      

       
        Split into  2  A length of  2  The rope of ,2 * 2 = 4
      
      
      
      

       
       
1.
      
      

Example 2

Input ：

Log in and copy

      
      

       
       5
      
      
      
      

       
       
1.
      
      

Return value ：

Log in and copy

      
      

       
       6
      
      
      
      

       
       
1.
      
      

explain ：

Log in and copy

      
      

       
        Cut into a length of  2  A rope and a length of  3  The rope of , The answer for 2*3=6
      
      
      
      

       
       
1.
      
      

Example 3

Input ：

Log in and copy

      
      

       
       874520
      
      
      
      

       
       
1.
      
      

Return value ：

Log in and copy

      
      

       
       908070737
      
      
      
      

       
       
1.
      
      

2. Code implementation ：

Log in and copy

      
      

       
       import java.util.*;
       
       
public class Solution {
       
       
    private long mod = 998244353;
       
       
    // Fast multiplication 
       
       
    private long fast(long x, long y){ 
       
       
        long res = 0;
       
       
        x %= mod;
       
       
        y %= mod;
       
       
        while(y != 0){
       
       
            if((y & 1L) != 0){
       
       
                // Addition instead of multiplication , To prevent cross-border 
       
       
                res += x; 
       
       
                if(res >= mod)
       
       
                    res -= mod;
       
       
            }
       
       
            y = y >> 1;
       
       
            x = x << 1;
       
       
            if(x >= mod)
       
       
                x -= mod;
       
       
        }
       
       
        return res;
       
       
    }
       
       
    // Fast power 
       
       
    long Pow(long x, long y){ 
       
       
        long res = 1;
       
       
        while(y != 0){
       
       
            // You can go up one more 
       
       
            if((y & 1L) != 0) 
       
       
                res = fast(res, x);
       
       
            // superposition 
       
       
            x = fast(x, x); 
       
       
            // Reduce the number of times 
       
       
            y = y >> 1; 
       
       
        }
       
       
        return res;
       
       
    }
       
       
    public long cutRope (long number) {
       
       
        // No more than 3 Direct calculation 
       
       
        if(number <= 3) 
       
       
            return number - 1;
       
       
        // aliquot 3
       
       
        if(number % 3 == 0) 
       
       
            return Pow(3, number / 3);
       
       
        // Last but not least 1
       
       
        else if(number % 3 == 1) 
       
       
            //4*3^{n-1}
       
       
            return fast(Pow(3, number / 3 - 1), 4); 
       
       
        // Last but not least 2
       
       
        else 
       
       
            //2*3^n
       
       
            return fast(Pow(3, number / 3), 2); 
       
       
    }
       
       
}
       
       

      
      
      
      

       
       
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.
       
       
44.
       
       
45.
       
       
46.
       
       
47.
       
       
48.
       
       
49.
       
       
50.
       
       
51.
       
       
52.
       
       
53.