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)

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

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 typedef long long ll;
 7 const int N = 30;
 8 const ll MOD=1000000007;
 9 struct Mat {
10     ll mat[N][N];
11     Mat()
12     {
13         memset(mat,0,sizeof(mat));
14     }
15     void clear(){
16         memset(mat,0,sizeof(mat));
17     }
18 };
19 
20 ll num[N];
21 int n, m,K;
22 Mat a;
23 
24 void init() {
25     //初始化状态转移矩阵
26     a.clear();
27     for(int j=0;j<m;j++)a.mat[0][j]=K*(K-1);
28     for(int i=1;i<m;i++)a.mat[i][i-1]=K;
29     for(int j=m;j<=2*m;j++)a.mat[m][j]=K*(K-1);
30     for(int i=m+1;i<=2*m;i++)a.mat[i][i-1]=K;
31     a.mat[2*m][m-1]=K;
32 }
33 
34 Mat operator * (Mat a, Mat b) {
35     Mat c;
36     for(int i=0;i<=2*m;i++){
37         for(int j=0;j<=2*m;j++){
38             for(int k=0;k<=2*m;k++){
39                 c.mat[i][j]+=b.mat[i][k]*a.mat[k][j];
40                 c.mat[i][j]%=MOD;
41             }
42         }
43     }
44     return c;
45 }
46 
47 Mat operator ^ (Mat a, int k) {
48     //初状态
49     Mat c;
50     c.mat[0][0]=1;
51     //快速幂
52     for(; k; k >>= 1) {
53         if(k&1) c = c*a;
54         a = a*a;
55     }
56     return c;
57 }
58 
59 int main() {
60     //freopen("data.in", "r", stdin);
61     int T;
62     scanf("%d",&T);
63     while(~scanf("%d%d%d",&n,&m,&K)) {
64         //初始化状态转移矩阵
65         init();
66         //矩阵快速幂，初始左矩阵不是单位矩阵，是初状态
67         a = a^n;
68         //得到最终矩阵后求答案
69         ll ans=0;
70         for(int i = m; i <= 2*m; ++i) {
71             ans+=a.mat[i][0];
72             ans%=MOD;
73         }
74         printf("%lld
", ans);
75     }
76     return 0;
77 }

HDU 5863

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

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
typedef long long ll;
const int N = 30;
const long long MOD=1000000007;
struct Mat {
    ll mat[N][N];
    Mat()
    {
        memset(mat,0,sizeof(mat));
    }
    void clear(){
        memset(mat,0,sizeof(mat));
    }
};

ll num[N];
int n, m,K;
Mat a;

void init() {
    //初始化状态转移矩阵
    a.clear();
    for(int j=0;j<m;j++)a.mat[0][j]=K*(K-1);
    for(int i=1;i<m;i++)a.mat[i][i-1]=K;
    for(int j=m;j<=2*m;j++)a.mat[m][j]=K*(K-1);
    for(int i=m+1;i<=2*m;i++)a.mat[i][i-1]=K;
    a.mat[2*m][m-1]=K;
}

Mat operator * (Mat a, Mat b) {
    Mat c;
    for(int i=0;i<=2*m;i++){
        for(int j=0;j<=2*m;j++){
            for(int k=0;k<=2*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[0][0]=1;
    //快速幂
    for(;k;k>>=1){
        if(k&1)c=c*a;
        a=a*a;
    }
    return c;
}

int main() {
    //freopen("data.in", "r", stdin);
        //初始化状态转移矩阵
        init();
        //矩阵快速幂，初始左矩阵不是单位矩阵，是初状态
        a = a^n;
    return 0;
}