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

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