0

問題の解決策を最適化するために、行列のべき乗法に関する優れたチュートリアルを説明または提案してください: バイトランドの万里の長城

私がアップロードしたソリューションは、この基礎となる方程式を使用した動的計画法に基づいています: [ 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;
    }

解の実行時間を最適化する行列累乗法を提案してください。

4

1 に答える 1

2

次のように定義されたシーケンスがある場合:

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^n、 O(Log(n)) で計算し、それを使用して を計算できu(n)ます。

于 2012-06-20T15:24:22.973 に答える