这道题机房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);
}
05-08 08:41