bzoj 1009:[HNOI2008]GT考试

这道题机房n多人好久之前就A了…… 我到现在才做出来……

一看就是DP＋矩阵乘法，但是一开始递推式推错了…… 正确的递推式应该是二维的……

　　f[i][j] 表示第准考证到第 i 位匹配了 j 位的方案数

　　f[i][j] = f[i][j-1] + f[i][k]  第k位可以转移到第 j 位

这就需要枚举 当前位是什么， 同是还需要求一个关于m 的KMP 就可以了

　　上代码：

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define M 25

using namespace std;

int n, m;

long long f[M] = {}, yu;

long long a[M][M] = {}, b[M][M] = {}, c[M][M];

int next[M] = {};

char s[M];

void make_next()

{

    int i = , j = -;

    next[] = -;

    while (i < m-)

        if (j == - || s[i] == s[j])

        {

            i++; j++;

            next[i] = j;

        }

        else j = next[j];

}

void cheng()

{

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

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

            c[i][j] = ;

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

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

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

        c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % yu;

    swap(c, b);

}

void fan()

{

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

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

            c[i][j] = ;

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

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

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

        c[i][j] = (c[i][j] + a[i][k] * a[k][j]) % yu;

    swap(c, a);

}

void mi(int n)

{

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

            b[i][i] = ;

    while (n)

    {

        if (n & ) cheng();

        n >>= ;

        fan();

    }

    swap(a, b);

}

int main()

{

    scanf("%d%d%I64d", &n, &m, &yu);

    scanf("%s", s);

    make_next();

    f[] = ;

    for (int i = ; i < m; ++i) //已经匹配 i 位 正在匹配第 i+1 位

    {

        for (int j = ''; j <= ''; ++j) // 第 i+1 位是 j

            if (j == s[i]) a[i+][i] ++; // success

            else // fail  find the last can pipei

            {

                int x = next[i];

                while (x != - && s[x] != j)

                    x = next[x];

                a[x+][i] ++;

            }

    }

    mi(n);

    long long ans = ;

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

    {

        long long zan = ;

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

            zan = (zan + f[j] * a[i][j]) % yu;

        ans = (ans + zan) % yu;

    }

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

}