超级超时的代码

#include <bits/stdc++.h>
using namespace std;
int n, m, k, p;
int p4[10]; // 4^i
// 所有状态是否可行
int ok[4096];
void init()
{
    p4[0] = 1;
    for (int i = 1; i <= 6; i++)
        p4[i] = p4[i - 1] * k;
    for (int sta = 0; sta <= p4[m] - 1; sta++)
    {
        bool flag = true;
        for (int i = 2; i <= m - 1; i++)
        {
            int a = sta / p4[i - 2] % k;
            int b = sta / p4[i - 1] % k;
            int c = sta / p4[i] % k;
            if (a == b && b == c)
            {
                flag = false;
                break;
            }
        }
        ok[sta] = flag;
    }
}
// f[i][now][pre]
// 前 i 行，第 i 行为 now，上一行为 pre 的方案数
int f[7][4096][4096];
void work()
{
    int ans1 = 0, ans2 = 0;
    for (int pre = 0; pre <= p4[m] - 1; pre++)
    {
        if (!ok[pre])
            continue;
        f[1][pre][0] = 1;
        ans1++;
        for (int now = 0; now <= p4[m] - 1; now++)
        {
            if (!ok[now])
                continue;
            f[2][now][pre] = 1;
            ans2++;
        }
    }
    if (n == 1)
    {
        cout << ans1 % p << "\n";
        return;
    }
    if (n == 2)
    {
        cout << ans2 % p << "\n";
        return;
    }
    int ans = 0;
    for (int i = 3; i <= n; i++)
    {
        cout << i << endl;
        for (int now = 0; now <= p4[m] - 1; now++)
        {
            if (!ok[now])
                continue;
            for (int pre = 0; pre <= p4[m] - 1; pre++)
            {
                if (!ok[pre])
                    continue;
                for (int t = 0; t <= p4[m] - 1; t++)
                {
                    if (!ok[t])
                        continue;
                    // 检查 now、pre、t 是否可行
                    bool flag = true;
                    for (int j = 0; j < m; j++)
                    {
                        if (now / p4[j] % k == pre / p4[j] % k &&
                            now / p4[j] % k == t / p4[j] % k)
                        {
                            flag = false;
                            break;
                        }
                    }
                    if (!flag)
                        continue;
                    // 可行就算进去
                    f[i][now][pre] += f[i - 1][pre][t];
                    if (f[i][now][pre] >= p)
                        f[i][now][pre] -= p;
                }
                if (i == n)
                {
                    ans += f[i][now][pre];
                    if (ans >= p)
                        ans -= p;
                }
            }
        }
    }
    cout << ans << "\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k >> p;
    init();
    work();
    return 0;
}