[BZOJ 1009][HNOI2008]GT考试

好劲啊这题……

首先先想DP的做法,我们用[tex]p[i][j][/tex]表示若字符串已匹配前缀[tex][1,i][/tex],有多少种方案使得追加上一个数后匹配[tex][1,j][/tex],这个用KMP可以很方便的求出(事实上暴力也可以)

然后再来看DP的做法,转移方程大致是这样的:

[tex]d[i][j]=\Sigma_{k=0}^{m-1}(d[i-1][k]\times p[k][j])[/tex]

但是n非常大,这么做注定要TLE。

不过看这个转移方程,是不是和矩阵乘法的定义很像?是的。

我们可以用一个[tex]1\times m[/tex]的矩阵[tex]D[/tex]来表示某一个阶段的DP值,我们可以把[tex]p[/tex]组织成一个[tex]m\times m[/tex]矩阵[tex]P[/tex]。然后我们可以发现:

[tex]D_i\times P=D_{i+1}[/tex]

由于矩阵乘法满足结合律,所以:

[tex]D_n=D_0\times P^n[/tex]

很明显可以快速幂搞出来。

代码:

/**************************************************************
    Problem: 1009
    User: danihao123
    Language: C++
    Result: Accepted
    Time:80 ms
    Memory:820 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef ull Matrix[22][22];
ull MOD;
#define REP(i,n) for(i=0;i<(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
#define CP_ARR(from,to) memcpy(to,from,sizeof(from))
 
inline void MatrixMul(Matrix A,Matrix B,int m,int n,int p,Matrix& res){
    register int i,j,k;
    Matrix C;
    CL_ARR(C,0);
    REP(i,m){
        REP(j,p){
            REP(k,n){
                C[i][j]=(C[i][j]+(A[i][k]*B[k][j])%MOD)%MOD;
            }
        }
    }
    CP_ARR(C,res);
}
void MatrixPow(Matrix A,int m,ull p,Matrix& res){
    Matrix a,temp;
    register int i;
    CL_ARR(a,0);
    memcpy(a,A,sizeof(a));
    CL_ARR(temp,0);
    REP(i,m){
        temp[i][i]=1;
    }
    while(p){
        if(1&p){
            MatrixMul(temp,a,m,m,m,temp);
        }
        p>>=1;
        MatrixMul(a,a,m,m,m,a);
    }
    CP_ARR(temp,res);
}
 
char buf[25];
int f[25];
int main(){
    register int i,u,j;
    register ull ret=0;
    ull n;
    int m;
    Matrix ans,P;
    scanf("%llu%d%llu",&n,&m,&MOD);
    scanf("%s",buf+1);
    CL_ARR(ans,0);
    ans[0][0]=1;
    CL_ARR(P,0);
    P[0][0]=9;P[0][1]=1;
    // f[0]=f[1]=0;
    for(i=1;i<m;i++){
        u=f[i];
        while(u && buf[u+1]!=buf[i+1]){
            u=f[u];
        }
        if(buf[u+1]==buf[i+1]){
            f[i+1]=u+1;
        }else{
            f[i+1]=0;
        }
        for(j=0;j<10;j++){
            u=i;
            while(u && buf[u+1]!=j+'0'){
                u=f[u];
            }
            if(buf[u+1]==j+'0'){
                P[i][u+1]=(P[i][u+1]+1)%MOD;
            }else{
                P[i][0]=(P[i][0]+1)%MOD;
            }
        }
    }
    MatrixPow(P,m,n,P);
    MatrixMul(ans,P,1,m,m,ans);
    for(i=0;i<m;i++){
        ret=(ret+ans[0][i])%MOD;
    }
    printf("%llu\n",ret);
    return 0;
}

[洛谷 P1962]斐波那契数列

线性代数的很多知识用一句欠揍的话形容就是:只可意会,不可言传。

友矩阵就是一个。友矩阵是一种应用于求递归数列的一种矩阵,作用是将一个旧的递归数列向量变成一个新的递归数列向量。友矩阵长相比较美(qi)观(pa),可以自行问度娘。

关于递归数列[tex]F[/tex],如果假设要用到的从前的信息可以组织为一个列向量[tex]F_{n-1}[/tex],若已知其友矩阵为[tex]A[/tex],则有下公式(这个推导其实并不难,如果你用解线性方程组的思维来看的话):

[tex]F_n=A\mul F_{n-1}[/tex]

可知(假设要用到的从前的信息为[tex]d[/tex]):

[tex]F_n=A^{n-d}*F_d[/tex]

然后我们发现求[tex]A^{n-d}[/tex]可以使用快速幂,这就简单了^_^

不过有个不错的小技巧:快速幂结果矩阵的初始值处理让人很头疼,不过可以直接使用单位矩阵,这样就相当于通常计算中的1辣~

代码:

#include <iostream>
#include <cstring>
using namespace std;
typedef unsigned long long ull;
typedef ull Matrix[2][2];
const ull MOD=1000000007;
#define REP(i,n) for(i=0;i<(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
#define CP_ARR(from,to) memcpy(to,from,sizeof(from))

inline void MatrixMul(Matrix A,Matrix B,int m,int n,int p,Matrix& res){
    Matrix C;
    register int i,j,k;
    CL_ARR(C,0);
    REP(i,m){
        REP(j,p){
            REP(k,n){
                C[i][j]=(C[i][j]+(A[i][k]*B[k][j])%MOD)%MOD;
            }
        }
    }
    CP_ARR(C,res);
}
void MatrixPow(Matrix A,ull x,Matrix& res){
    Matrix a,temp;
    register int i;
    bool used=false;
    memcpy(a,A,sizeof(a));
    CL_ARR(temp,0);
    temp[0][0]=1;
    temp[1][1]=1;
    while(x){
        if(1&x){
            MatrixMul(temp,a,2,2,2,temp);
        }
        x>>=1;
        MatrixMul(a,a,2,2,2,a);
    }
    CP_ARR(temp,res);
}
Matrix Q={{0,1},{1,1}};
Matrix Fib={{1,0},{1,0}};
int main(){
    ull n;
    ios::sync_with_stdio(NULL);
    cin.tie(0);
    cin>>n;
    if(n<=2){
        cout<<1<<endl;
    }else{
        MatrixPow(Q,n-2,Q);
        MatrixMul(Q,Fib,2,2,1,Fib);
        cout<<Fib[1][0]<<endl;
    }
    return 0;
}