矩陣冪方法

任何人都可以請解釋或暗示的矩陣冪的方法，一些好的教程，以優化問題的解決方案： 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

回答

相關問題