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

Question

有没有人可以解释或者推荐一些关于矩阵求幂方法的好教程，以优化问题的解决方案：great wall of byteland

我上传的解决方案是基于以下基本方程的动态编程: f(n) = f(n-1) + 4*f(n-2) + 2*f(n-3)，但该解决方案给了我超过时间限制的错误。

这是我构建的代码：

    #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)))。

然后，您可以在O( A^n (N))中计算Log，并使用它来计算u(n)。