schtonn

schtonn

0%

复杂矩阵快速幂

Posted on Edited on Valine:

前置知识

矩阵快速幂。这是一点比较复杂的应用。

题目

已知递推公式： \[ \begin{array}{rcl} F(n,1)&=&F(n-1,2)+2F(n-3,1)+5,\\ F(n,2)&=&F(n-1,1)+3F(n-3,1)+2F(n-3,2)+3 \end{array} \]

初始值为：\(F(1,1)=2,F(1,2)=3,F(2,1)=1,F(2,2)=4,F(3,1)=6,F(3,2)=5\)。

输入 \(n\)，输出 \(F(n,1)\) 和 \(F(n,2)\)，由于答案可能很大，你只需要输出答案除以 \(99999999\) 的余数。 \[ \begin{array}{rcl} F(n+1,1)&=&F(n,2)+2F(n-2,1)+5,\\ F(n+1,2)&=&F(n,1)+3F(n-2,1)+2F(n-2,2)+3 \end{array} \]

矩阵

注意由于递推式里有常数，所以矩阵中要加上一个 \(1\)，当然它在状态的转移间不需要改变，只是用来给上面的式子加个常数。 \[ \left[ \begin{array}{c} F_{n+1,1}\\F_{n+1,2}\\F_{n,1}\\F_{n,2}\\F_{n-1,1}\\F_{n-1,2}\\1 \end{array} \right]= \left[ \begin{array}{lr} 0&1&0&0&2&0&5\\ 1&0&0&0&3&2&3\\ 1&0&0&0&0&0&0\\ 0&1&0&0&0&0&0\\ 0&0&1&0&0&0&0\\ 0&0&0&1&0&0&0\\ 0&0&0&0&0&0&1\\ \end{array} \right]\times\left[ \begin{array}{c} F_{n,1}\\F_{n,2}\\F_{n-1,1}\\F_{n-1,2}\\F_{n-2,1}\\F_{n-2,2}\\1 \end{array} \right] \]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include "bits/stdc++.h"
using namespace std;
const long long N=90;
const long long mod=99999999;
long long n,tlen=7,initial[N+2]={6,5,1,4,2,3,1};
struct matrix{
    long long v[N+2][N+2];
    long long x,y;
    void clear(){
        for(long long i=0;i<N;i++){
            for(long long j=0;j<N;j++){
                v[i][j]=0;
            }
        }
    }
}t,I,ans,f;
long long base[N+2][N+2]={
    {0,1,0,0,2,0,5},
    {1,0,0,0,3,2,3},
    {1,0,0,0,0,0,0},
    {0,1,0,0,0,0,0},
    {0,0,1,0,0,0,0},
    {0,0,0,1,0,0,0},
    {0,0,0,0,0,0,1},
};
ostream&operator<<(ostream&ous,matrix a){  
    for(long long i=0;i<a.x;i++){
        for(long long j=0;j<a.y;j++){
            ous<<a.v[i][j]<<' ';
        }
        ous<<endl;
    }
    return ous;
}
matrix operator+(matrix a,matrix b){
    matrix c;
    c.clear();
    if(a.x!=b.x||a.y!=b.y){
        cout<<"error adding!"<<endl;
        return c;
    }
    long long x=a.x,y=a.y;
    c.x=x;
    c.y=y;
    for(long long i=0;i<x;i++){
        for(long long j=0;j<y;j++){
            c.v[i][j]=(a.v[i][j]+b.v[i][j])%mod;
        }
    }
    return c;
}
matrix operator*(matrix a,matrix b){
    matrix c;
    c.clear();
    if(a.y!=b.x){
        cout<<"error multiplying!"<<endl;
        return c;
    }
    long long x=a.x,y=b.y,z=a.y;
    c.x=x;
    c.y=y;
    for(long long i=0;i<x;i++){
        for(long long j=0;j<y;j++){
            c.v[i][j]=0;
            for(long long k=0;k<z;k++){
                c.v[i][j]=(c.v[i][j]+a.v[i][k]*b.v[k][j])%mod;
            }
        }
    }
    return c;
}
void init(){
    t.x=t.y=tlen;
    I.x=I.y=tlen;
    f.x=tlen;
    f.y=1;
    for(long long i=0;i<tlen;i++){
        for(long long j=0;j<tlen;j++){
            t.v[i][j]=base[i][j];
        }
    }
    for(long long i=0;i<tlen;i++){
        f.v[i][0]=initial[i];
    }
    for(long long i=0;i<tlen;i++)I.v[i][i]=1;
}
int main(){
    cin>>n;
    init();
    if(n==1){
        cout<<2<<endl<<3<<endl;
    }else if(n==2){
        cout<<1<<endl<<4<<endl;
    }else if(n==3){
        cout<<6<<endl<<5<<endl;
    }else{
        long long cnt=n-3;
        ans=I;
        while(cnt){
            if(cnt&1)ans=ans*t;
            t=t*t;
            cnt>>=1;
        }
        ans=ans*f;
        cout<<ans.v[0][0]<<endl<<ans.v[1][0]<<endl;
    }
    return 0;
}