14- II. 剪绳子 II

思路:

与14- I. 剪绳子相比,多了取模。
因为最初后果以指数模式增长,可能会超int32 甚至int64,

若只在最终后果求余:

因而须要逐渐求余,求余具备论断如下:

(xy)%p = [(x%p)(y%p)]%p(x^a)%p = ((···(x%p)*x%p)····*x%p)

因而采纳循环求余的办法:
每乘一次3,取一次模,最初return再取一次模。

操作:


官网:
n=4没有操作,能够优化掉

  • 留神:

    • 最终后果res用long型来接管
    • 最终return res*n%1000000007,就思考了余数为0,1,2以及4的状况。