题意：
要你求在N * M的图中每个格子涂上黑色或白色的方案数对P取模后的结果，要满足每个2*2的区域里不能只有一种颜色。
N≤10100 ,M≤5,P≤10000

分析：
看到N这么大，M这么小，很快想到快速幂。若从上往下做的话，每一行对它有影响的只有它的上一行，所以可以先搜索出转移矩阵，然后快速幂（注意高精度）。

#include <cstdio>
#include <cstring>
using namespace std;const int M = 1 << 5,N = 110;
struct jz {int s[M][M];
} s,re;
struct gjd {int len,s[N];
} n;
int m,P,len;
bool p[2][M];
char in[N];bool check(int x,int t) {if (x == 1) return true;if (p[0][x] != t || p[0][x - 1] != t || p[1][x - 1] != t) return true;return false;
}void dfs(int st,int dep,int h,int last) {if (h == 0) {if (dep > m) {dfs(0,1,2,st);return;}p[0][dep] = true;dfs(st << 1 | 1,dep + 1,h,0);p[0][dep] = false;dfs(st << 1,dep + 1,h,0);}else {if (dep > m) {s.s[last][st] = 1;return;}if (check(dep,1)) {p[1][dep] = true;dfs(st << 1 | 1,dep + 1,h,last);p[1][dep] = false;}if (check(dep,0)) dfs(st << 1,dep + 1,h,last);}
}jz calc(jz a,jz b) {jz c;memset(c.s,0,sizeof(c.s));for (int k = 0;k <= len;k ++) {for (int i = 0;i <= len;i ++) {for (int j = 0;j <= len;j ++) {c.s[i][j] = (c.s[i][j] + a.s[i][k] * b.s[k][j] % P) % P;}}}return c;
}void div() {for (int i = n.len;i;i --) {if (i > 1) n.s[i - 1] += (n.s[i] & 1) * 10;n.s[i] /= 2;}while (!n.s[n.len]) n.len --;
}void fast() {if (n.len == 1 && n.s[1] == 1) return;int flag = 0;if (n.s[1] & 1) flag = 1;div();fast();re = calc(re,re);if (flag) re = calc(re,s);
}void init() {scanf(" %s%d%d",&in,&m,&P);n.len = strlen(in);int i;for (i = 0;i < n.len;i ++) if (in[i] == ' ') break;for (int j = i - 1;j >= 0;j --) n.s[i - 1 - j + 1] = in[j] - '0';
}int main() {init();if (n.len == 1 && n.s[1] == 1) printf("%d",(1 << m) % P);else {n.s[1] --;int i = 1;while (n.s[i] < 0) n.s[i] += 10,n.s[i + 1] --,i ++;while (!n.s[n.len]) n.len --;len = (1 << m) - 1;dfs(0,1,0,0);memcpy(re.s,s.s,sizeof(s.s));fast();int ans = 0;for (int i = 0;i <= len;i ++) {for (int j = 0;j <= len;j ++) ans = (ans + re.s[i][j]) % P;}printf("%d",ans);}
}