题意：

将一根长度为 切割为每段至少长度为5的若干段，求总的切割方案数？（5+6和6+5算两种不同的方案）

解法一（暴力枚举，不可AC）：

我们可以定义递归函数 表示当前绳子长度为 ，进行递归地切割，最后 时统计答案。

class Solution {
public:
    const int mod=998244353;
    int ans;
    void dfs(int i){
        if(i<0)return;//长度不能为负数
        if(i==0){//刚好切割完
            ans=(ans+1)%mod;
            return;
        }
        for(int j=5;j<=i;j++){
            dfs(i-j);
        }
    }
    int messageCount(int N) {
        ans=0;//多测清零
        dfs(N);
        return ans;
    }
};

时间复杂度：
不会算，递推式如下

复杂度大概为 ，其中
空间复杂度： ，递归的深度是 级别的，故总的空间复杂度为

解法二（动态规划）：

我们设 表示切割长度为 的绳子的方案数，我们枚举最后一段绳子的长度 ，

显然有： ，其中

class Solution {
public:
    const int mod=998244353;
    int messageCount(int N) {
        int* f=new int[N+1]{0};//动态分配内存
        int* sum=new int[N+1]{0};
        f[0]=1;//边界
        sum[0]=1;//边界
        for(int i=1;i<=N;i++){
            if(i>=5)f[i]=sum[i-5];
            sum[i]=(sum[i-1]+f[i])%mod;
        }
        return f[N];
    }
};

时间复杂度： ，我们只需要进行一次 的循环，循环体内部是的，故总的时间复杂度为
空间复杂度： 数组都是 级别的，故总的空间复杂度为

解法三（矩阵快速幂）：

根据解法二可得：
，
由
可得
因此我们可以构造矩阵乘法：

由于矩阵乘法具有结合律，因此我们可以利用矩阵快速幂先求出 ，然后再左乘上事先预处理的 即可求出 和 ，最后利用 就是所求答案。
代码：

class Solution {
public:
    static const int mod=998244353;
    struct mat{
        int** A;
        int n,m;//n行，m列
        inline mat(int n,int m):n(n),m(m){
            A=new int*[n];
            for(int i=0;i<n;i++){
                A[i]=new int[m]{0};
            }
        }
        inline mat operator * (const mat& other)const{//矩阵乘法
            mat ret(n,other.m);
            for(int i=0;i<n;i++){
                for(int j=0;j<other.m;j++){
                    for(int k=0;k<m;k++){
                        ret.A[i][j]+=1ll*A[i][k]*other.A[k][j]%mod;
                        ret.A[i][j]%=mod;
                    }
                }
            }
            return ret;
        }
    };
    inline mat ksm(mat a,int b){
        mat ret(a.n,a.m);
        for(int i=0;i<a.n;i++){
            ret.A[i][i]=1;
        }
        while(b){
            if(b&1){
                ret=ret*a;
            }
            a=a*a;
            b>>=1;
        }
        return ret;
    }
    int messageCount(int N) {
        mat x(5,1);
        x.A[4][0]=1;//sum[1]
        x.A[3][0]=1;//sum[2]
        x.A[2][0]=1;//sum[3]
        x.A[1][0]=1;//sum[4]
        x.A[0][0]=2;//sum[5]
        mat y(5,5);
        y.A[0][0]=1,y.A[0][4]=1;
        y.A[1][0]=1;
        y.A[2][1]=1;
        y.A[3][2]=1;
        y.A[4][3]=1;
        if(N<=5){
            if(N==5)return 1;
            return 0;
        }
        y=ksm(y,N-5);
        mat ans=x*y;//x左乘y
        return (ans.A[0][0]-ans.A[1][0]+mod)%mod;//sum[n]-sum[n-1]
    }
};

时间复杂度： ，矩阵乘法的复杂度可视为 ，矩阵快速幂需要进行 次矩阵乘法运算，故总的时间复杂度为
空间复杂度： ，仅需要保存 级别个数的大小为 的矩阵和大小为 的矩阵，故总的空间复杂度为