矩阵快速幂板子和矩阵优化DP

1303. 斐波那契前 n 项和 （矩阵快速幂板子）

debug 了 半天，终于还是写出来了，矩阵乘法从下标0开始从乘比较好写。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

ll F[3],n,m;//n = 3 时,F_0
ll A[3][3]={
    {1,0,0},
    {1,1,1},
    {1,1,0},
};

void print(ll a[][3]){
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
}

void print(ll a[3]){
    for(int j=0;j<3;j++){
        cout<<a[j]<<" ";
    }
    cout<<endl;
}

void mul(ll f[3],ll a[3],ll b[3][3]){// 1*3 3*3
    ll res[3]={0};
    for(int j=0;j<3;j++){
        for(int k=0;k<3;k++){
            res[j] = (res[j] + a[k]*b[k][j])%m;
        }
    }
    memcpy(f,res,sizeof res);
}

// 我都想到要重载mul了，为啥不自己写呢？

void mul(ll f[][3],ll a[][3],ll b[][3]){
    ll res[3][3]={0};
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
                res[i][j] = (res[i][j] + a[i][k]*b[k][j])%m; 
            }
        }
    }
    memcpy(f,res,sizeof res);
}



void qmi(ll f[3],ll b){//3*3 自乘
    while(b){
        if(b&1){
            mul(f,f,A);// 1*3  =  (1*3) * (3 *3 )
        }
        b>>=1;
        mul(A,A,A);// 3*3 * 3 * 3 = 3*3
    }
}


int main(){
    cin>>n>>m;
    F[0] = 2;// 前两项的和
    F[1] = 1;
    F[2] = 1;

    n-=2;

    qmi(F,n);

    cout<<F[0]<<endl;
    return 0;
}

1305. GT考试 （矩阵乘法优化DP）

一眼不会。

$f[i][j]$ 表示长串匹配到第 $i$ 位，短串最多匹配到第 $j$ 位的所有合法方案的方案数。

$ans={\sum }_{i=0}^{m-1}f[n][i]$

有的时候我总是纠结，是从当前向后还是从后向前呢？

考虑 $f[i][j]$ 是如何由前面的状态转移过来的。

考虑 $f[i-1][k]$ 怎么转移到 $f[i][j]$ 。

枚举第 $i$ 位是什么字符。

$f[i][j]={\sum }_{k=0}^{m-1}f[i-1][k]\ast g[k][j]$ 。

$g[k][j]$ 表示一个匹配了长度为 $k$ 的串，有多少种加入一个数字的方式，使得匹配长度变成 $j$ 。

模式串是给定的，如何得到 $g[k][j]$ 。

暴力枚举长度 $K$ 和 待加入的数字 。$O(m^2)$

在自己思考并参考了大佬的代码之后，有了40pts的暴力代码。

#include <iostream>
#include <cstring>
#include <algorithm>

#define debug(x) cout<<#x<<":"<<x<<endl
using namespace std;

const int N = 30;

int n,m,K,ne[N];
int g[N][N];
int f[1100000][N];
char p[N];

int main(){
    cin>>n>>m>>K;
    scanf("%s",p+1);
    for(int i=2,j=0;i<=m;i++){
        while(j&&p[j+1]!=p[i])j=ne[j];
        if(p[j+1]==p[i])j++;
        ne[i]=j;
    }
    
    for(int i=0;i<=m;i++){//得从0开始。
        for(char ch='0';ch<='9';ch++){
            /*
            当前已经匹配了i个字符，下一个字符是ch
            */
            int j=i;
            while(j&&p[j+1]!=ch)j=ne[j];
            if(p[j+1]==ch)j++;
            if(j<m)//不能完全匹配。
                g[i][j]++;
        }
    }

    f[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<m;j++){
            for(int k=0;k<m;k++){
                f[i][j] = (f[i][j] + f[i-1][k] * g[k][j]) % K;
            }
        }
    }
    int ans=0;
    for(int i=0;i<m;i++){
        ans = (ans + f[n][i])%K;
    }
    cout<<ans<<endl;
    return 0;
}

如何用矩阵优化递推？

让我们求 $f[n][iin[0,m]] $ ，$f[i][j]$ 如何变成 $F[i]$ ？

没搞懂，只能看视频了

$g_{x,y}$ 表示对于模式串的匹配从第 $y$ 位转移到第 $x$ 位的方案数。
$$\begin{gathered} f[i][0]=g_{0,0}\ast f[i-1][0]+g_{0,1}f[i-1][1]+... \\ f[i][1]=g_{1,0}\ast f[i-1][0]+g_{1,1}f[i-1][1]+... \\ f[i][2]=g_{2,0}\ast f[i-1][0]+g_{2,1}f[i-1][1]+... \\ ... \\ f[i][m-1]=g_{m-1,0}\ast f[i-1][0]+g_{m-1,1}f[i-1][1]+... \end{gathered}$$
将左侧所有的 $f[i][0\sim m-1]$ 看成一个向量 $F[i]$ ，把右侧所有的 $g_{x,y}$ 看成系数 $A$ ，把

$f[i-1][0\sim m-1]$ 看成矩阵 $F[i-1]$ 。又因为 $g_{x,y}$ 不受 $i$ 的影响，对于给定的模式串，$g_{x,y}$ 是定值，所以 $A$ 是定值。

满足 $F[i]=A\ast F[i-1]$ ，有：

$F[n]=A^n\ast F[0]$ ，可以使用矩阵快速幂优化。

分析到这还有问题，F矩阵一开始怎么存

$F$ 是一个 $1\ast m$ 的向量，

int F[30];

初始化 $F[0]=1$ 。

然后我写了两个矩阵乘法，不懈努力之下终于AC！

#include <iostream>
#include <cstring>
#include <algorithm>

#define debug(x) cout<<#x<<":"<<x<<endl
using namespace std;

const int N = 30;

int n,m,K,ne[N];
int g[N][N];
char p[N];
int F[N];

void mul(int f[N],int a[N],int b[N][N]){// 1*m =  (1*m) * (m*m)
    int t[N]={0};

    for(int j=0;j<m;j++){
        for(int k=0;k<m;k++){
            t[j] = (t[j] + a[k] * b[k][j])%K;
        }
    }

    memcpy(f,t,sizeof t);
}

void mul(int f[N][N],int a[N][N],int b[N][N]){// 1*m =  (1*m) * (m*m)
    int t[N][N]={0};
    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++){
            for(int k=0;k<m;k++){
                t[i][j] = (t[i][j] + a[i][k] * b[k][j])%K;
            }
        }
    }
    memcpy(f,t,sizeof t);
}

int qmi(int t){
    F[0]=1;
    while(t){
        if(t&1){
            mul(F,F,g);
        }
        mul(g,g,g);
        t>>=1;
    }
    int ans=0;
    for(int i=0;i<m;i++){
        ans = (ans + F[i]) %K;
    }
    return ans;
}

int main(){
    cin>>n>>m>>K;
    scanf("%s",p+1);
    for(int i=2,j=0;i<=m;i++){
        while(j&&p[j+1]!=p[i])j=ne[j];
        if(p[j+1]==p[i])j++;
        ne[i]=j;
    }
    
    for(int i=0;i<=m;i++){//得从0开始。
        for(char ch='0';ch<='9';ch++){
            /*
            当前已经匹配了i个字符，下一个字符是ch
            */
            int j=i;
            while(j&&p[j+1]!=ch)j=ne[j];
            if(p[j+1]==ch)j++;
            if(j<m)//不能完全匹配。
                g[i][j]++;
        }
    }
    cout<<qmi(n);
    return 0;
}

看y总代码的启示，可以把 mul 合并成一个。

非常漂亮的代码
#include <iostream>
#include <cstring>
#include <algorithm>

#define debug(x) cout<<#x<<":"<<x<<endl
using namespace std;

const int N = 30;

int n,m,K,ne[N];
int g[N][N];
char p[N];
int F[N][N];//虽然开了两维，但只有F[0][1~N]使用了 

void mul(int f[N][N],int a[N][N],int b[N][N]){// 1*m =  (1*m) * (m*m)
    int t[N][N]={0};
    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++){
            for(int k=0;k<m;k++){
                t[i][j] = (t[i][j] + a[i][k] * b[k][j])%K;
            }
        }
    }
    memcpy(f,t,sizeof t);
}

int qmi(int t){
    F[0][0]=1;
    while(t){
        if(t&1){
            mul(F,F,g);
        }
        mul(g,g,g);
        t>>=1;
    }
    int ans=0;
    for(int i=0;i<m;i++){
        ans = (ans + F[0][i]) %K;
    }
    return ans;
}

int main(){
    cin>>n>>m>>K;
    scanf("%s",p+1);
    for(int i=2,j=0;i<=m;i++){
        while(j&&p[j+1]!=p[i])j=ne[j];
        if(p[j+1]==p[i])j++;
        ne[i]=j;
    }
    for(int i=0;i<=m;i++){//得从0开始。
        for(char ch='0';ch<='9';ch++){
            /*
            当前已经匹配了i个字符，下一个字符是ch
            */
            int j=i;
            while(j&&p[j+1]!=ch)j=ne[j];
            if(p[j+1]==ch)j++;
            if(j<m)//不能完全匹配。
                g[i][j]++;
        }
    }
    cout<<qmi(n);
    return 0;
}

最后

以上就是个性樱桃最近收集整理的关于矩阵快速幂板子和矩阵优化DP的全部内容，更多相关矩阵快速幂板子和矩阵优化DP内容请搜索靠谱客的其他文章。