hdu5863_dp+矩阵快速幂-白红宇

hdu5863_dp+矩阵快速幂

阅读量：4598 次

发布时间：2019-06-09

本文共 1995 字，大约阅读时间需要 6 分钟。

题目链接：

题意：

题目大概说用k个不同的字母，有多少种方法构造出两个长度n最长公共子串长度为m的字符串。

思路

n的规模达到了10亿，而且又是方案数，自然就想到构造矩阵用快速幂解决。

考虑用DP解决可以这么表示状态：

dp[i][j]表示两个字符串前i个字符都构造好了并且它们后面的j个字符相同的方案数

状态的转移就是，末尾j个相同的可以转移到0个相同的也能转移到j+1个相同的（前提是j<m）。

而对于这个状态可以构造矩阵去转移，即一个(m+1)*(m+1)的矩阵，矩阵i行j列表示从末尾i个相同转移到末尾j个相同的方案数，而该矩阵的n次幂的第0行的和就是长度n的字符串末尾各个情况的方案数。

不过样表示状态最后求出来不是要求的，因为LCS小于m的也会包含于其中。那么减去小于m的方案数不就OK了！

即至少包含m个相同公共子串的方案数 - 至少包含m-1个相同公共子串的方案数 = 恰好包含m个相同公共子串的方案数

于是，一样再构造一个m*m的矩阵求n次幂，就OK了。

f[i][j]表示构造好前i个，最后j个相同的方案数

f[i][j]=f[i-1][j-1]*k 【最后一位有k种方案相同】

f[i][0]=sigma(f[i-1][j])*k*(k-1) j=0~m 【倒数第二位相同最后一位不同有k*(k-1)种方案】

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #include 
               
                11 #include 
                12 using namespace std;13 #define mod 100000000714 typedef long long LL;15 16 struct Mat{17 int m[11][11];18 int len;19 };20 Mat mul(Mat a, Mat b){21 Mat m;22 memset(m.m, 0, sizeof(m.m));23 m.len=a.len;24 for(int i=0; i<=m.len; ++i){25 for(int j=0; j<=m.len; ++j){26 for(int k=0; k<=m.len; ++k){27 m.m[i][j]+=(LL)a.m[i][k]*b.m[k][j]%mod;28 m.m[i][j]%=mod;29 }30 }31 }32 return m;33 }34 int solve(int n, int m, int k)35 {36 Mat res, base;37 memset(res.m, 0, sizeof(res.m));38 memset(base.m, 0, sizeof(base.m));39 res.len = m, base.len = m;40 for(int i = 0; i <= m; i++)41 res.m[i][i] = 1;42 for(int i = 0; i <= m; i++)43 base.m[i][0] = k * k - k;44 for(int i = 0; i < m; i++)45 base.m[i][i+1] = k;46 while(n)47 {48 if(n & 1)49 res = mul(res, base);50 base = mul(base, base);51 n >>= 1;52 }53 int ans = 0;54 for(int i = 0; i <= m ; i++){55 ans += res.m[0][i];56 ans %= mod;57 }58 return ans;59 }60 int main()61 {62 int t,n,m,k;63 scanf("%d",&t);64 while(t--){65 scanf("%d%d%d",&n,&m,&k);66 int res = solve(n, m, k) - solve(n, m -1, k);67 res = (res + mod) % mod;68 printf("%d\n", res);69 }70 return 0;71 }

View Code

转载于:https://www.cnblogs.com/luomi/p/5793469.html

你可能感兴趣的文章