题目的主要信息:
  • 把一根长度为nn的绳子分成mm段,每段长度都是整数
  • 求每段长度乘积的最大值
  • 由于答案过大,请对 998244353 取模
举一反三:

学习完本题的思路你可以解决如下题目:

JZ14. 剪绳子

方法:快速幂+快速乘法(推荐使用)

知识点1:贪心思想

贪心思想属于动态规划思想中的一种,其基本原理是找出整体当中给的每个局部子结构的最优解,并且最终将所有的这些局部最优解结合起来形成整体上的一个最优解。

知识点2:分治:

分治即“分而治之”,“分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的子问题,子问题继续按照这样划分,直到问题可以被轻易解决;“治”指的是将子问题单独进行处理。经过分治后的子问题,需要将解进行合并才能得到原问题的解,因此整个分治过程经常用递归来实现。

思路:

根据均值不等式,有:n1+n2+...+nmmn1n2...nmm\frac{n_1+n_2+...+n_m}{m}\geq \sqrt[m]{n_1n_2...n_m},等号当且仅当n1=n2=n3=...nmn_1=n_2=n_3=...n_m时成立,因为加法部分和是固定的绳子总长度,因此要使乘积最大,应该以相等的长度等分成多段。

如果将绳子按照每段长度为xx等分成mm段,则n=mxn=mx,乘积为xmx^m,因为有xm=xnx=(x1x)nx^m=x^{\frac{n}{x}}=(x^{\frac{1}{x}})^n因此当x1xx^{\frac{1}{x}}取最大值时取最大值。

y=x1xy=x^{\frac{1}{x}},即求这个函数的极值即可直到绳子等分成长度为多少可以使乘积最大。根据取对数、求导、求极值等一系列数学操作,得驻点为x0=ex_0=e,即极大值需要将绳子分成每段e,但是绳子长度只能是整数,靠近e的只有2 和3,二者分别代入公式,发现当x=3x=3是,乘积达到最大。

因此后续,使用贪心思想,不断将绳子分成每段长度为3即可,不足3的可以考虑,如果最后剩余的是2,直接乘上,如果最后剩余的是1,则取出一个3组成4分成长度为2的两段,因为22>132*2>1*3

具体做法:

  • step 1:将问题分成三种情况,使用快速幂和快速乘法直接计算幂。
  • step 2:n整除3的时候,即可以全部完成分成长度为3的小段,一共n/3n/3段,计算3n/33^{n/3}即可。
  • step 3:n除3余1的时候,需要拿出一个3个1组合称,一共n/31n/3-1段长度为3的,2段长度为2的,计算223n/312*2*3^{n/3-1}即可;
  • step 4:n除3余2的时候,直接将剩下长度为2的段乘在之前的乘积上,计算23n/32*3^{n/3}即可。

计算幂为了缩短时间,采用快速幂加快速乘法优化:

快速幂:如果我们要计算5105^{10},常规的算法是55=255*5=25,然后再255=12525*5=125,如此往下,一共是99次运算,即n1n-1次。但是我们可以考虑这样:55=255*5=25(二次)、2525=62525*25=625(四次)、625625=...625*625=...(八次),这是一个二分的思维,运算次数缩减到了log2nlog_2n次,公式如下:

alt

快速乘法:直接计算xax^a会超出long的表示范围,因此我们可以考虑用加法来代替乘法,并在这其中取模。就比如ab=a(b1+b2+b3+...)a*b=a*(b_1+b_2+b_3+...),其中bib_i是数字bb的二进制各位,假设a=5a=5b=110101b=110101,我们有ab=a(1000001+100001+10000+1001+100+11)a*b=a*(100000*1+10000*1+1000*0+100*1+10*0+1*1),如下表所示可以换成加法运算并在加法中取模:

alt

图示:

alt

Java实现代码:

import java.util.*;
public class Solution {
    private long mod = 998244353;
    //快速乘法
    private long fast(long x, long y){ 
        long res = 0;
        x %= mod;
        y %= mod;
        while(y != 0){
            if((y & 1L) != 0){
                //加法代替乘法,防止越界
                res += x; 
                if(res >= mod)
                    res -= mod;
            }
            y = y >> 1;
            x = x << 1;
            if(x >= mod)
                x -= mod;
        }
        return res;
    }
    //快速幂
    long Pow(long x, long y){ 
        long res = 1;
        while(y != 0){
            //可以再往上乘一个
            if((y & 1L) != 0) 
                res = fast(res, x);
            //叠加
            x = fast(x, x); 
            //减少乘次数
            y = y >> 1; 
        }
        return res;
    }
    public long cutRope (long number) {
        //不超过3直接计算
        if(number <= 3) 
            return number - 1;
        //能整除3
        if(number % 3 == 0) 
            return Pow(3, number / 3);
        //最后剩余1
        else if(number % 3 == 1) 
            //4*3^{n-1}
            return fast(Pow(3, number / 3 - 1), 4); 
        //最后剩余2
        else 
            //2*3^n
            return fast(Pow(3, number / 3), 2); 
    }
}

C++实现代码:

class Solution {
public:
    long long mod = 998244353;
    //快速乘法
    long long fast(long long x, long long y){ 
        long long res = 0;
        x %= mod;
        y %= mod;
        while(y){
            if(y & 1){
                //加法代替乘法,防止越界
                res += x; 
                if(res >= mod)
                    res -= mod;
            }
            y = y >> 1;
            x = x << 1;
            if(x >= mod)
                x -= mod;
        }
        return res;
    }
    //快速幂
    long long Pow(long long x, long long y){ 
        long long res = 1;
        while(y){
            //可以再往上乘一个
            if(y & 1) 
                res = fast(res, x);
            //叠加
            x = fast(x, x); 
            //减少乘次数
            y = y >> 1; 
        }
        return res;
    }
    long long cutRope(long long number) {
        //不超过3直接计算
        if(number <= 3) 
            return number - 1;
        //能整除3
        if(number % 3 == 0) 
            return Pow(3, number / 3);
        //最后剩余1
        else if(number % 3 == 1) 
            //4*3^{n-1}
            return fast(Pow(3, number / 3 - 1), 4); 
        //最后剩余2
        else 
            //2*3^n
            return fast(Pow(3, number / 3), 2); 
    }
};

Python实现代码:

class Solution:
    def __init__(self):
        self.mod = 998244353
        
    #快速乘法
    def fast(self, x: int, y: int) -> int: 
        res = 0
        x %= self.mod
        y %= self.mod
        while y:
            if y & 1:
                #加法代替乘法,防止越界
                res += x
                if res >= self.mod:
                    res -= self.mod
            y = y >> 1
            x = x << 1
            if x >= self.mod:
                x -= self.mod
        return res
    
    #快速幂
    def Pow(self, x: int, y: int) -> int: 
        res = 1
        while y:
            #可以再往上乘一个
            if y & 1: 
                res = self.fast(res, x)
            #叠加
            x = self.fast(x, x) 
            #减少乘次数
            y = y >> 1
        return res
    
    def cutRope(self , number: int) -> int:
        #不超过3直接计算
        if number <= 3: 
            return number - 1
        #能整除3
        if number % 3 == 0: 
            return self.Pow(3, number // 3)
        #最后剩余1
        elif number % 3 == 1:
            #4*3^{n-1}
            return self.fast(self.Pow(3, number // 3 - 1), 4)
        #最后剩余2
        else: 
            #2*3^n
            return self.fast(self.Pow(3, number // 3), 2)

复杂度分析:

  • 时间复杂度:O(log2n)O(log_2n),快速幂相当于二分法,因此复杂度为O(log2n)O(log_2n)
  • 空间复杂度:O(1)O(1),常数级变量,无额外辅助空间