y总视频里所说的预计算方式。可以将时间复杂度为降为$O(N^2*26)$

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 55;
const int module = 1e9 + 7;

int f[MAXN][MAXN];
int trans[MAXN][26];
char p[MAXN];
int N, ne[MAXN];

int main() {
    cin >> N >> p + 1;
    int m = strlen(p + 1);

    for (int i = 2, j = 0; i <= m; ++i) {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) ++j;
        ne[i] = j;
    }

    for (int i = 0; i < m; ++i) {
        for (int k = 'a'; k <= 'z'; ++k) {
            int u = i;
            while (u && p[u + 1] != k) u = ne[u];
            if (p[u + 1] == k) ++u;
            trans[i][k - 'a'] = u;
        }
    }

    f[0][0] = 1;
    for (int i = 1; i <= N; ++i) {
        for (char k = 'a'; k <= 'z'; ++k) {
            for (int j = 0; j < m; ++j) 
            {
                int u = trans[j][k - 'a'];
                if (u != m) f[i][u] = (f[i][u] + f[i - 1][j]) % module;
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < m; ++i)  ans = (ans + f[N][i]) % module;
    cout << ans << endl;
    return 0;
}