P2233 [HNOI2002]公交车路线

洛咕原题

dp->矩阵乘法

首先我们可以得出一个状态转移方程 f[i][j]=f[i-1][j-1]+f[i-1][j+1]

蓝后发现，我们可以把这转化为一个8*8的转移矩阵

然后跑一遍矩阵快速幂即可

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

struct matrix{
    int a[9][9];
    matrix(){memset(a,0,sizeof(a));}
    matrix operator * (matrix &tmp){
        matrix c;
        for(int i=1;i<=8;++i)
            for(int j=1;j<=8;++j)
                for(int k=1;k<=8;++k)
                    c.a[i][j]=(c.a[i][j]+a[i][k]*tmp.a[k][j]%1000)%1000;
        return c;
    }
    matrix ksm(matrix x,int y){
        matrix ans;
        for(int i=1;i<=8;++i) ans.a[i][i]=1;
        for(;y;y>>=1){
            if(y&1) ans=ans*x;
            x=x*x;
        }
        return ans;
    }
}st,p;
int main()
{
    st.a[1][1]=1; //初始矩阵，A站为起点
//其实初始矩阵是8*1的矩阵，然而我懒得写qwq
    int n; scanf("%d",&n);
    p.a[2][1]=p.a[8][1]=1;
    p.a[1][2]=p.a[3][2]=1;
    p.a[2][3]=p.a[4][3]=1;
    p.a[3][4]=1; 
    p.a[4][5]=p.a[6][5]=1;
    p.a[7][6]=1; 
    p.a[6][7]=p.a[8][7]=1;
    p.a[7][8]=p.a[1][8]=1; //转移矩阵（注意题目说到E站的时候就会停下来）
    p=p.ksm(p,n);
    st=st*p;
    printf("%d",st.a[1][5]); //到E站的总方案数
    return 0;
}