看题n的数据，很明显告诉你了是矩阵乘法， 且矩阵阶数为2^m。
这里n要稍稍写一下高精度（减1， 除以2）。
用dp[i][j]表示前i层，最后层状态为j的合法个数。
很容易推出方程。
水水的题，速A
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int n[103], m;
const int N = 1<<5;
int mod;
int M;
void add(int &a, int b) {
a += b;
if(a >= mod) a -= mod;
}
void mult(int a[N][N], int b[N][N]) { // 乘法函数
int c[N][N] = {0};
int i, j, k;
for(k = 0; k < M; k++)
for(i = 0; i < M; i++)
for(j = 0; j < M; j++)
add(c[i][j], a[i][k]*b[k][j] % mod);
for(i = 0; i < M; i++)
for(j = 0; j < M; j++)
a[i][j] = c[i][j];
}
int A[N][N];
bool ok(int a, int b) { // 判是否合法
int i;
for(i = 0; i <m-1; i++) {
int x = a&(1<<i), y = a&(1<<(i+1));
int u = b&(1<<i), v = b&(1<<(i+1));
if(x && y && u && v) return 0;
if(!x && !y && !u && !v) return 0;
}
return 1;
}
void build() { // 建初始A矩阵
int i, j;
for(i = 0; i < M; i++)
for(j = 0; j < M; j++)
A[i][j] = ok(i, j);
}
void div2(int *a) { // 除以2
int ans[103] = {0};
int i, res = 0;
for(i = a[0]; i >= 0; i--) {
ans[i] = (a[i]+res*10)/2;
res = (a[i]+res*10)%2;
}
ans[0] = a[0];
if(ans[a[0]] == 0) ans[0]--;
for(i = 0; i <= ans[0]; i++)
a[i] = ans[i];
}
void sub(int *a) { // 减1
int i;
for(i = 1; i <= a[0]; i++) {
a[i] --;
if(a[i] < 0) a[i] += 10;
else break;
}
if(a[a[0]] == 0) a[0]--;
if(!a[0]) a[0]++;
}
char s[103];
int ans[N][N];
int main() {
int i, j;
scanf("%s%d%d", s, &m, &mod);
n[0] = strlen(s);
for(i = 1; i <= n[0]; i++)
n[i] = s[n[0]-i]-'0';
for(i = 0; i < N; i++)
for(j = 0; j < N; j++)
ans[i][j] = (i==j);
M = (1<<m);
build();
sub(n);
while(n[0]) {
if(n[1]&1) mult(ans, A);
mult(A, A);
div2(n);
}
int sum = 0;
for(i = 0; i < (1<<m); i++)
for(j = 0; j < (1<<m); j++)
add(sum, ans[i][j]);
printf("%d\n", sum);
return 0;
}