c++ - 用于运行时优化的矩阵求幂方法

Question

任何人都可以请解释或建议一些关于矩阵求幂方法的好教程，以优化问题的解决方案： byteland 的长城

我上传的解决方案是基于动态规划的，具有以下基本方程：[ f(n) = f(n-1) + 4*f(n-2) + 2*f(n-3) ] 但解决方案是me 超出时间限制错误。

这是我构建的代码：

    #include<iostream>
    #define num 1000000007
    using namespace std;
    int main(){
        int t;
        cin>>t;
        while(t--){
            int n;
            cin>>n;
            if(n<=3){
                switch(n){
                    case 1:
                        cout<<1<<endl;
                        break;
                    case 2:
                        cout<<5<<endl;
                        break;
                    case 3:
                        cout<<11<<endl;
                        break;
                }
            }
            else{
                int a=1 , b=5 , c=11 ;
                int next;
                for(int i=4;i<=n;i++){
                    next = (c + 4*b + 2*a)%num ;
                    a = b;
                    b = c;
                    c = next;
                }
                cout<<next<<endl;
            }
        }
        return 0;
    }

请建议用于优化解决方案运行时间的矩阵求幂方法。

Answer 1

如果您有一个由以下定义的序列：

u(0) to u(d-1) are given
for n > d u(n)=a(1)*u(n-1)+…+a(d)*u(n-d)

然后让 A 是由以下定义的伴随矩阵：

A(i,j) = a(d+1-j) if i = d
         1 if i+1 = j
         0 otherwise

然后让uinit = transpose(u(0) … u(d-1))

你有A^n*uinit = transpose(u(n) … u(n+d-1))（你可以自己验证A*transpose(u(n) … u(n+d-1)) = transpose(u(n+1) … u(n+d))）。

然后你可以计算A^nO(Log(n)) 并用它来计算u(n).