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

3个数越多答案越大，所以n%3有三种情况:

余数为0直接做3^(n/3)

余数为1做4*3^((n-4)/3)

余数为2做2*3^((n-2)/3)

代码技巧部分：因为指数会很大如果用Math的函数效率低，这种情况可以用快速幂去做，比如a^n次方要n次的相乘，快速幂只需要logn次

import java.util.*;


public class Solution {
  //快速幂函数求a^n次方的结果
    long pow(long a, long n){
        final int MOD = 998244353;;
        long ans = 1;

        while(n>0){
           if(n%2 == 1)ans = (ans*a)%MOD;
           a = (a*a)%MOD;
           n/=2;
       }
       return ans;
    }
    
    public long cutRope (long number) {
        if(number == 2)return 1;
        if(number == 3)return 2;
        
        if(number % 3 == 0)return pow(3,number/3);
        else if(number % 3 == 1)return 4*pow(3,(number-4)/3)%998244353;
        else return (2*pow(3,(number-2)/3))%998244353;
    }
}