T4 时空の穿越：矩阵

题意简化

给定序列 $F$，有：

$$\begin{equation*} F_i= \begin{cases} 1, & 1\le (i\le 5)\\ F_{i-1}+2\times F_{i-2}+3\times F_{i-3}+5\times F_{i-4}+8\times F_{i-5}, & (i \ge 6)\\ \end{cases} \end{equation*}$$

求 $Ans$，其中：

$$\begin{equation*} Ans= \begin{cases} F_N\mod 2^{32}, & F_N\mod 2^{32}\lt 2^{31}\\ (F_N\mod 2^{32})-2^{32}, & F_N\mod 2^{32}\ge 2^{31}\\ \end{cases} \end{equation*}$$

---

暴力代码

很显然的一个递推式子。直接模拟一下即可。

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
ull _,n;
ull dp[1005];
int main(){
    cin>>_;
    while(_--){
        cin>>n;
        dp[1]=dp[2]=dp[3]=dp[4]=dp[5]=1;
        for(ull i=6;i<=n;i++) dp[i]=
            dp[i-1]+
            (dp[i-2]<<1)+
            (dp[i-3]<<1)+dp[i-3]+
            (dp[i-4]<<2)+dp[i-4]+
            (dp[i-5]<<3);
        cout<<(int)dp[n]<<'\n';
    }
    return 0;
}

时间复杂度：$O(TN)$

空间复杂度：$O(N)$

预计得分：$30pts$

---

空间优化

显然 $dp_i$ 只与 $dp_{i-1},dp_{i-2},dp_{i-3},dp_{i-4},dp_{i-5}$ 有关。所以我们只需要记录 $6$ 个数即可。

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
ull _,n,a,b,c,d,e,t;
int main(){
    cin>>_;
    while(_--){
        cin>>n;
        a=b=c=d=e=1;
        for(ull i=6;i<=n;i++){
            t=a;
            a=b;
            b=c;
            c=d;
            d=e;
            e+=(c<<1)+(b<<1)+b+(a<<2)+a+(t<<3);
        }
        cout<<(int)e<<'\n';
    }
    return 0;
}

时间复杂度：$O(TN)$

空间复杂度：$O(1)$

预计得分：$30pts$

正解

由线性递推联想到矩阵加速。

回忆一下斐波那契数列的矩阵加速：定义矩阵：

$$\begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix}$$

得到：

$$M \times \begin{bmatrix} F_{n-1} \\ F_{n-2} \end{bmatrix} =\begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix}$$

根据矩阵乘法，得到：

$$M_{1,1} \times F_{n-1}+ M_{1,2} \times F_{n-2} = F_n \\ M_{2,1} \times F_{n-1} + M_{2,2} \times F_{n-2} = F_{n-1}$$

所以得到：

$$M = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$$

于是问题转化为：

$$\begin{bmatrix} 1 \\ 1 \end{bmatrix} \times M^{n-1}$$

矩阵快速幂即可。

类似地，我们定义矩阵：

$$\begin{bmatrix} F_n \\ F_{n-1} \\ F_{n-2} \\ F_{n-3} \\ F_{n-4} \end{bmatrix}$$

得到：

$$M \times \begin{bmatrix} F_{n-1} \\ F_{n-2} \\ F_{n-3} \\ F_{n-4} \\ F_{n-5} \end{bmatrix} = \begin{bmatrix} F_n \\ F_{n-1} \\ F_{n-2} \\ F_{n-3} \\ F_{n-4} \end{bmatrix}$$

根据矩阵乘法，得到：

$$M_{1,1} \times F_{n-1} + M_{1,2} \times F_{n-2} + M_{1,3} \times F_{n-3} + M_{1,4} \times F_{n-4} + M_{1,5} \times F_{n-5}=F_n\\ M_{2,1} \times F_{n-1} + M_{2,2} \times F_{n-2} + M_{2,3} \times F_{n-3} + M_{2,4} \times F_{n-4} + M_{2,5} \times F_{n-5}=F_{n-1}\\ M_{3,1} \times F_{n-1} + M_{3,2} \times F_{n-2} + M_{3,3} \times F_{n-3} + M_{3,4} \times F_{n-4} + M_{3,5} \times F_{n-5}=F_{n-2}\\ M_{4,1} \times F_{n-1} + M_{4,2} \times F_{n-2} + M_{4,3} \times F_{n-3} + M_{4,4} \times F_{n-4} + M_{4,5} \times F_{n-5}=F_{n-3}\\ M_{5,1} \times F_{n-1} + M_{5,2} \times F_{n-2} + M_{5,3} \times F_{n-3} + M_{5,4} \times F_{n-4} + M_{5,5} \times F_{n-5}=F_{n-4}$$

所以得到：

$$M = \begin{bmatrix} 1 & 2 & 3 & 5 & 8\\ 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ \end{bmatrix}$$

于是问题转化为：

$$M^{n-5} \times \begin{bmatrix} 1\\ 1\\ 1\\ 1\\ 1 \end{bmatrix}$$

矩阵快速幂即可。

#include<bits/stdc++.h>
using namespace std;
#define uint unsigned int
#define ull unsigned long long
#define rep(i,l,r) for(int i=l;i<=r;i++)
struct mat{
    int n,m;
    uint a[7][7];
    inline void empty(){
        this->n=this->m=0;
        memset(this->a,0,sizeof(this->a));
        return;
    }
    inline void resize(const int &n,const int &m){
        empty();
        this->n=n,this->m=m;
        return;
    }
    inline void unit(const int &n){
        empty();
        this->n=this->m=n;
        rep(i,1,n) this->a[i][i]=1;
        return;
    }
    inline void fill(const int &x){
        rep(i,1,this->n) rep(j,1,this->m) this->a[i][j]=x;
        return;
    }
    inline mat operator*(const mat &a){
        mat res;
        res.resize(this->n,a.m);
        rep(i,1,res.n) rep(j,1,res.m) rep(k,1,this->m) res.a[i][j]+=this->a[i][k]*a.a[k][j];
        return res;
    }
    inline void operator*=(const mat &a){
        *this=*this*a;
        return;
    }
};
int _;
ull n;
mat x,y,res;
int main(){
    cin>>_;
    while(_--){
        cin>>n;
        if(n>5) n-=5;
        else{
            cout<<"1\n";
            continue;
        }
        x.resize(5,1);
        x.fill(1);
        y.resize(5,5);
        y.a[1][1]=y.a[2][1]=y.a[3][2]=y.a[4][3]=y.a[5][4]=1;
        y.a[1][2]=2,y.a[1][3]=3,y.a[1][4]=5,y.a[1][5]=8;
        res.unit(5);
        while(n){
            if(n&1) res*=y;
            y*=y;
            n>>=1;
        }
        res*=x;
        cout<<(int)(res.a[1][1])<<'\n';
    }
    return 0;
}

时间复杂度：$O(T \log N)$

空间复杂度：$O(1)$

预计得分：$100pts$