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

class Solution {
public:
    //  // 迭代快速幂
    // long long fast(int a, int b)
    // {
    //     if (b == 0)  return 1;
    //     if (b%2 == 1) return a*fast(a, b-1)%998244353;
    //     else {
    //         long long tmp = fast(a,b/2);
    //         return (tmp*tmp)%998244353;
    //     } 
    // }

    // long long cutRope(long long number) {
    //     // write code here
    //     // 评论区有很多关于均值不等式最值证明，当剪每段3时候，乘积最大
    //     // 若一个一个相乘，乘积有点大，故快速幂解决  3^6 ==  3^3 x 3^3 ,瞬间从6次变成了乘以2次
    //     // if(number <= 4) return number;// 由于段数必须大于1，故这里不能这么写
    //     if(number == 2) return 1;
    //     if(number == 3) return 2;
    //     int count_3 = number/3;
    //     if (number%3 == 1) {//余数为1时，不改变整体，倒不如取个3凑成4更佳
    //         return 4*fast(3, count_3-1)%998244353;
    //     }
    //     else if(number%3 == 2)
    //     {
    //         return (2*fast(3, count_3))%998244353;
    //     }
    //     return fast(3, count_3);

    //     // 数据级太大了，不能用这个
    //     // vector<long long> dp(number+1, 0);
    //     // dp[1] = 1;
    //     // dp[2] = 2;
    //     // dp[3] = 3;
    //     // dp[4] = 4;
    //     // for(int i = 5; i <= number; ++i)
    //     // {
    //     //     for(int j = 1; j < i; ++j)
    //     //     {
    //     //         dp[i] = max(dp[i], j*dp[i-j]);
    //     //     }
    //     // }
    //     // return dp[number]%998244353; 
    // }
  // 我是写不出这种了。。。，谁会计算个数考虑使用二进制运算。。。
    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);
    }
};