传送门：点击打开链接
题意：摆放小象，使得所有棋子的攻击范围的位置都是空白
思路：m这么小n这么大很明显是在提示你要用快速幂，问题就在于如何构造矩阵了，然而这题看似矩阵太复杂了，别说的云里雾里，但是仔细一分析，，就是发现并没有那么难..
我们把m看作棋盘的列数，n看作棋盘的行数，下面我们只考虑两行棋子
那么对于相邻两行的同一列的两个位置，现在我们考虑这两个位置可以怎么放。
1.如果这两个位置是在第一列，那么可以是任意的，即4种状态都是可以的,01,10,11,00
2.如果不是在第一列，设当前在第i列
首先，无论之前是什么情况，第i列可以都不放，也可以都放
除了上面两种摆放方法外，那么剩下的摆放方法跟跟i-1列已经放的棋子是有联系的
如果i-1列的两个位置的状态是一样的，即都放了棋子，或者都没放棋子，那么对于第i列，我就可以在第i列中选择其中一个位置摆放棋子，另一个位置不摆放棋子
如果i-1列的两个位置状态不一样，也就是说，一个摆放了棋子，一个没有摆放棋子，那么在第i列，在i-1列摆放了棋子的右边那个位置是可以摆放棋子的，对应的另一行的位置是不能摆放棋子的
总的来说况，就是一句话，如果两个棋子想在对角线摆放，那么这两个棋子就必须是连通的（边相邻才算连通）
所以我们把矩阵给构造出来，剩下的就是直接快速幂撸一发了
#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck printf("fuck")
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;const int matMX = 128 + 5;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;struct Mat {int m, n;LL S[matMX][matMX];Mat(int a, int b) {m = a;n = b;memset(S, 0, sizeof(S));}Mat(int a, int b, LL w[][matMX]) {m = a;n = b;for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {S[i][j] = w[i][j];}}}
};Mat mat_mul(Mat A, Mat B) {Mat C(A.m, B.n);for(int i = 0; i < A.m; i++) {for(int j = 0; j < B.n; j++) {for(int k = 0; k < A.n; k++) {C.S[i][j] = (C.S[i][j] + A.S[i][k] * B.S[k][j]) % mod;}}}return C;
}Mat Blank(int m, int n) {Mat ret(m, n);for(int i = 0; i < m; i++) {ret.S[i][i] = 1;}return ret;
}Mat mat_pow(Mat A, LL b) {Mat ret = Blank(A.m, A.n);while(b) {if(b & 1) ret = mat_mul(ret, A);A = mat_mul(A, A);b >>= 1;}return ret;
}LL S[matMX][matMX];
void DFS(int m, int cnt, int x, int y) {if(cnt == m) {S[x][y] = 1;return;}DFS(m, cnt + 1, x << 1, y << 1);DFS(m, cnt + 1, x << 1 | 1, y << 1 | 1);if(cnt) {if((x & 1) ^ (y & 1) == 0) {DFS(m, cnt + 1, x << 1, y << 1 | 1);DFS(m, cnt + 1, x << 1 | 1, y << 1);} else if((x & 1) && !(y & 1)) {DFS(m, cnt + 1, x << 1 | 1, y << 1);} else {DFS(m, cnt + 1, x << 1, y << 1 | 1);}} else {DFS(m, cnt + 1, x << 1 | 1, y << 1);DFS(m, cnt + 1, x << 1, y << 1 | 1);}
}int main() {int m, n; //FIN;while(~scanf("%d%d", &n, &m)) {DFS(m, 0, 0, 0);Mat A(1 << m, 1 << m, S), B(1 << m, 1);memset(B.S, 0, sizeof(B.S));B.S[0][0] = 1;Mat ret = mat_mul(mat_pow(A, n), B);LL ans = 0;for(int i = 0; i < (1 << m); i++) {ans += ret.S[i][0];ans %= mod;}printf("%I64d\n", ans);}return 0;
}