题解 | #剪绳子（进阶版）#

数组+快速幂：由减绳子基础班可以得知，当绳子长度与3取余为1时，取出两个2米的绳子最优；当绳子长度与3取余为2时，取出一个2米的绳子最优。那么剩下绳子长度必然是3的整数倍b=len/3。结果就是a^b。但是b的数值非常大，暴力求解必然超时，所以此时采用快速幂进行求解。就是将b换成2的各个次幂之和。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number long长整型 
     * @return long长整型
     */
    public long cutRope (long number) {
        // write code here
        if(number <= 3) {
            return number - 1;
        }
        int MOD = 998244353;
        long res = 1;
        if(number % 3 == 1) {
            res *= 4;
            number -= 4;
        }
        if(number % 3 == 2) {
            res *= 2;
            number -= 2;
        }
        long x = number / 3;
        long k = 3;
        while(x != 0) {
            long u = x & 1;
            if(u == 1) {
                res = (res * k) % MOD;
            }
            k = (k * k) % MOD;
            x >>= 1;
        }
        return res;
    }
}