83.md

剪绳子（进阶版）

题目

给你一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（ m 、 n 都是整数， n > 1 并且 m > 1 ， m <= n ），每段绳子的长度记为 k[1],...,k[m] 。请问 k[1]k[2]...*k[m] 可能的最大乘积是多少？例如，当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18

• 由于答案过大，请对 998244353 取模
• 进阶：空间复杂度 O(1)， 时间复杂度 O(logn)

示例

• 输入：4

• 返回值：4

• 说明：拆分成 2 个长度为 2 的绳子，2 * 2 = 4

• 输入：5

• 返回值：6

• 说明：剪成一个长度为 2 的绳子和一个长度为 3 的绳子，答案为2*3=6

思路

func CutRope(number int64) int64 {
	if number == 2 {
		return 1
	}
	if number == 3 {
		return 2
	}
	var res int64 = 1
	for number > 4 {
		res *= 3
		res %= 998244353
		number -= 3
	}
	return res * number % 998244353
}

实现

func cutRope(number int64) int64 {
	if number == 2 {
		return 1
	}
	if number == 3 {
		return 2
	}
	cnt := number / 3
	if number%3 == 0 {
		return pow(cnt) % 998244353
	} else if number%3 == 1 {
		cnt--
		return 2 * 2 * pow(cnt) % 998244353
	} else if number%3 == 2 {
		return 2 * pow(cnt) % 998244353
	}
	return 4
}

func pow(cnt int64) int64 {
	if cnt == 0 {
		return 1
	}
	if cnt == 1 {
		return 3
	}
    part := pow(cnt / 2)
	if cnt%2 == 0 {
		return part * part % 998244353
	} else {
		return 3 * part * part % 998244353
	}
}