[HNOI2008]GT考试矩阵优化DP

～～～题面～～～

题解：

一开始看觉得很难，理解了之后其实还挺容易的。

首先我们考虑朴素DP：

　　令f[i][j]表示长串到了第i项，与不吉利数字（模式串）匹配到了第j项的方案。

　　显然ans = f[n][0] + f[n][1] + …… + f[n][m-1]；

　　可以肉眼看出f[1][0] = 9, f[1][1] = 1；

　　于是我们考虑如何转移。

　　首先我们观察到，f[i-1][j]如果要给f[i][k]做贡献，那么就要使得匹配到j位变成匹配到k位。

　　我们设g[j][k]表示原本是匹配到j位，加入一个新数字后变成匹配到k位的方案数。这里的匹配到x位的x是指匹配到模式串的第x位。

　　那么我们有转移方程：$f[i][j] = \sum_{i=0}^{m-1}f[i-1][k]*g[k][j]$

　　那么如何求解g[i][j]呢？

　　可以考虑KMP。但是由于数据比较小，所以这里就直接用暴力了。

　　首先我们枚举i表示当前已经匹配到了第i位（i可以为0）

　　然后我们枚举新加进来的数

　　再我们再枚举可能会匹配 l 位，从高位开始枚举，

　　然后暴力检验看是不是可以刚好匹配到 l 位，注意要从后面开始匹配，如果没解释清楚，看代码就知道了。

　　如果可以刚好匹配到 l 位，那么我们就++g[i][l]并break

然后我们考虑优化：

　　观察转移方程$f[i][k] = \sum_{i=0}^{m-1}f[i-1][j]*g[j][k]$.

　　emmmm,..与矩阵相乘完美吻合。。。。

　　所以用矩阵加速一下就好啦

 #include<bits/stdc++.h>

 using namespace std;

 #define R register int

 #define AC 23

 int n, m, p, ans;

 char s[AC], tmp[AC];

 struct matrix{

     int s[AC][AC];

 }f, g, box;

 void pre()

 {

     scanf("%d%d%d", &n, &m, &p);

     scanf("%s", s + );

     if(n == )

     {

         if(m == ) ans = ;

         else ans = ;

         ans %= p;

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

         exit();

     }

     //g.s[0][1] = 1, g.s[0][0] = 9;//因为g是匹配数，所以行也可能是0

     for(R i = ; i < m ; i++)//枚举已经匹配到了哪一位

     {

         tmp[i] = s[i];

         for(R j = ; j <= ; j++)//枚举下一位是什么

         {

             tmp[i + ] = j + '';

             int t, k = ;

             for(R l = i + ; l >= ; l--)//枚举最多可以匹配几位

             {

                 t = l, k = i + ;

                 while(s[t] == tmp[k] && t) --t, --k;

                 if(!t)

                 {

                     if(l != m) ++g.s[i][l];

                     break;

                 }

             }

         }

     }

 }

 void build()

 {

     f.s[][] = , f.s[][] = ;

 }

 void cal1()

 {

     for(R j = ; j < m; j++)//枚举是第一行的第几列，注意0也是合法的

     {

         box.s[][j] = ;

         for(R l = ; l < m; l++)//枚举f的对应行和g的对应列

             box.s[][j] += f.s[][l] * g.s[l][j];

         box.s[][j] %= p;

     }

     f = box;

 }

 void cal2()

 {

     for(R i = ; i < m; i++)

         for(R j = ; j < m; j++)

         {

             box.s[i][j] = ;

             for(R l = ; l < m; l++)

                 box.s[i][j] += g.s[i][l] * g.s[l][j];

             box.s[i][j] %= p;

         }

     g = box;

 }

 void qpow(int have)

 {

     while(have)

     {

         if(have & ) cal1();

         cal2();

         have >>= ;

     }

 }

 void work()

 {

     for(R i = ; i < m; i++) ans += f.s[][i];

     ans %= p;

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

 }

 int main()

 {

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

     pre();

     build();

     qpow(n - );

     work();

     fclose(stdin);

     return ;

 }

巴特西

[HNOI2008]GT考试矩阵优化DP

最新文章

热门文章

巴特西

[HNOI2008]GT考试 矩阵优化DP

最新文章

热门文章

[HNOI2008]GT考试矩阵优化DP