HDU 5863 cjj's string game (矩阵乘法优化递推)

题目大意：用k种字符构建两个长度为n的字符串（每种字符有无限多个），要求对应位置字符相同的连续子串最长长度为m，问方法数。

其中k,n,m是输入，n(1<=n<=1000000000), m(1<=m<=10), k(1<=k<=26).

对题目解释更详细点儿，如下两串

123456

223466

这个的“对应位置字符相同的连续子串最长长度”是3，是字符串“234”。

解题思路，这题一看就是DP或者组合数学，但是不会组合数学，只能DP了
dp[i][j]表示前i个字符，最后j个位置相同的方法数

第三维01表示该状态是否包含了至少一个长度为m的“对应位置相同子串”

dp[i][j][0]=dp[i-1][j-1][0]*k （0<j<m）
dp[i][0][0]=sum(dp[i-1][0到m-1][0])*k*(k-1)
dp[i][j][1]=dp[i-1][j-1][1]*k （0<j<=m）
dp[i][0][1]=(sum(dp[i-1][0到m][1])+dp[i-1][m-1][0])*k*(k-1)

由于第一维范围过大，且只和前一个状态有关，很明显想到矩阵乘法优化递推。完整代码如下：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 typedef long long ll;

 const int N = ;

 const ll MOD=;

 struct Mat {

     ll mat[N][N];

     Mat()

     {

         memset(mat,,sizeof(mat));

     }

     void clear(){

         memset(mat,,sizeof(mat));

     }

 };

 ll num[N];

 int n, m,K;

 Mat a;

 void init() {

     //初始化状态转移矩阵

     a.clear();

     for(int j=;j<m;j++)a.mat[][j]=K*(K-);

     for(int i=;i<m;i++)a.mat[i][i-]=K;

     for(int j=m;j<=*m;j++)a.mat[m][j]=K*(K-);

     for(int i=m+;i<=*m;i++)a.mat[i][i-]=K;

     a.mat[*m][m-]=K;

 }

 Mat operator * (Mat a, Mat b) {

     Mat c;

     for(int i=;i<=*m;i++){

         for(int j=;j<=*m;j++){

             for(int k=;k<=*m;k++){

                 c.mat[i][j]+=b.mat[i][k]*a.mat[k][j];

                 c.mat[i][j]%=MOD;

             }

         }

     }

     return c;

 }

 Mat operator ^ (Mat a, int k) {

     //初状态

     Mat c;

     c.mat[][]=;

     //快速幂

     for(; k; k >>= ) {

         if(k&) c = c*a;

         a = a*a;

     }

     return c;

 }

 int main() {

     //freopen("data.in", "r", stdin);

     int T;

     scanf("%d",&T);

     while(~scanf("%d%d%d",&n,&m,&K)) {

         //初始化状态转移矩阵

         init();

         //矩阵快速幂，初始左矩阵不是单位矩阵，是初状态

         a = a^n;

         //得到最终矩阵后求答案

         ll ans=;

         for(int i = m; i <= *m; ++i) {

             ans+=a.mat[i][];

             ans%=MOD;

         }

         printf("%lld\n", ans);

     }

     return ;

 }

HDU 5863

然后写这个主要是想记录下矩阵乘法的板子

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

const int N = ;

const long long MOD=;

struct Mat {

    ll mat[N][N];

    Mat()

    {

        memset(mat,,sizeof(mat));

    }

    void clear(){

        memset(mat,,sizeof(mat));

    }

};

ll num[N];

int n, m,K;

Mat a;

void init() {

    //初始化状态转移矩阵

    a.clear();

    for(int j=;j<m;j++)a.mat[][j]=K*(K-);

    for(int i=;i<m;i++)a.mat[i][i-]=K;

    for(int j=m;j<=*m;j++)a.mat[m][j]=K*(K-);

    for(int i=m+;i<=*m;i++)a.mat[i][i-]=K;

    a.mat[*m][m-]=K;

}

Mat operator * (Mat a, Mat b) {

    Mat c;

    for(int i=;i<=*m;i++){

        for(int j=;j<=*m;j++){

            for(int k=;k<=*m;k++){

                c.mat[i][j]+=b.mat[i][k]*a.mat[k][j];

                c.mat[i][j]%=MOD;

            }

        }

    }

    return c;

}

Mat operator ^ (Mat a, int k) {

    //初状态

    Mat c;

    c.mat[][]=;

    //快速幂

    for(;k;k>>=){

        if(k&)c=c*a;

        a=a*a;

    }

    return c;

}

int main() {

    //freopen("data.in", "r", stdin);

        //初始化状态转移矩阵

        init();

        //矩阵快速幂，初始左矩阵不是单位矩阵，是初状态

        a = a^n;

    return ;

}

巴特西

HDU 5863 cjj's string game (矩阵乘法优化递推)

最新文章

热门文章