矩阵幂方法

任何人都可以请解释或暗示的矩阵幂的方法，一些好的教程，以优化问题的解决方案： great wall of byteland 矩阵幂方法

我上传的解决方案是基于动态规划与这个基础方程： [f（n）= f（n-1）+ 4 * f（n-2）+ 2 * f（n-3）] 但是解决方案给了我Time Limit Exceeded Error。

这是我建立了代码：

#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; 
    }

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

来源

2012-06-20 c_sharma

[按平方排列的指数]（http://en.wikipedia.org/wiki/Exponentiation_by_squaring）可能是一个很好的起点。 –

为了澄清，通过“矩阵求幂”，你是否试图计算A^n或e^A？ –

@OliCharlesworth：我不确定，但是与问题有关的是什么 –

如果你有一个序列定义为：

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（Log（n））中的A^n并使用它来计算u(n)。

来源

2012-06-20 15:24:22 Thomash

回答

相关问题