Link

T399750 Cell kingdom（Hard)

Qustion

第一天产生 \(1\) 个细胞，之后的每一天，一个细胞都会分裂成 \(8\) 个和自己一样的细胞，每个细胞在第三天都会自爆并且带走当天产生的 \(6\) 个细胞，求第 \(x\) 天有多少细胞

Solution

我们设 \(F[i]\) 表示第 \(i\) 天产生的新细胞个数

那么可以得出递推式

\[\begin{aligned} F[i]& =(F[i-1]+F[i-2])\times 7+F[i-2]\times 6 \\& =F[i-1]\times7+F[i-2] \end{aligned}\]

然后考虑如何化简这个递归式

我们可以构造处一个矩阵

\[\begin{bmatrix}F_{i-2}& F_{i-1}\end{bmatrix} \begin{bmatrix}0&1\\1&7\end{bmatrix}=\begin{bmatrix}F_{i-1}& F_{i-2}+7F_{i-1}\end{bmatrix}=\begin{bmatrix}F_{i-1}& F_{i}\end{bmatrix} \]

这样我们就得到了把递推式转化成了矩阵乘法

考虑到矩阵乘法的结合律，我们可以把相同的矩阵先乘起来，直接用快速幂处理

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL TT=1e9+7;
struct Mar{
    LL a[2][2];
    Mar(){memset(a,0,sizeof a);}
};
Mar operator * (Mar A,Mar B){
    Mar ret;
    for(int i=0;i<2;i++)
    for(int j=0;j<2;j++)
    for(int k=0;k<2;k++){
        ret.a[i][j]+=(A.a[i][k]*B.a[k][j]%TT+TT)%TT;
        ret.a[i][j]=(ret.a[i][j]+TT)%TT;
    }
    return ret;
}
Mar Pow(Mar a,LL b){
    Mar ret;
    ret.a[0][0]=1;
    ret.a[1][1]=1;
    while(b){
        if(b&1) ret=ret*a;
        a=a*a;
        b>>=1;
    }
    return ret;
}
int main(){
    freopen("B.in","r",stdin);
    LL N;
    cin>>N;
    if(N==1){printf("1\n");return 0;}
    if(N==2){printf("8\n");return 0;}
    Mar base,st,ed;
    base.a[0][1]=1;base.a[1][0]=1;base.a[1][1]=7;
    st.a[0][0]=1;st.a[0][1]=7;
    Mar ans=Pow(base,N-2);
    ed=st*ans;
    cout<<(ed.a[0][0]+ed.a[0][1])%TT;
    return 0;
}