• 知识点：线性DP，状压DP，预处理 辅助转移的技巧

首先看到 n*n 的方格而且只能向右下方向走，而且还是求解方案数，就可以想到是很经典的线性DP模型；
但这道题有一点不一样，有些点是不能走的，因为有马看着，其次就是，马的状态也不一定，可能也会被吃掉，那么对应的一些格子是可以走的

所以我们很自然的就可以想到用不用记录一下马的剩余状态，来判断一些格子能还是不能走呢？

这就需要我们再在二维dp的基础上再开一维，用于记录马的状态，题目中马的数量只有 10，$2^{10}$ = 1024
空间和时间的压力都是可以承受的

但是又有一个问题，O(n * n * 1000) 这时候的复杂度就已经很高了，1e7，然后我还得再在每次循环后把每匹马的状态处理出来(*10)，然后再枚举每个马的周围八个方向(*8)，然后再枚举别的马看有没有别蹄(*10)…

此时我们惊人的发现复杂一度逼近 1e10，这显然是不能接受的，这是就要进行预处理了：

预先处理一个数字，判断当马的状态是 state 的时候哪些格子是安全的，也是一个和 f 数组一样大的数组，但是有了它我们就可以不用处理那么多东西，代码也会好写很多。

参考代码如下，大家也可以有别的写法，譬如直接枚举转移点周围的八个点看有没有马，这样也许就不用预处理g数组了，只是那样的代码太难写了，我没有调出来，就不放了。

void solve()
{int n, m;cin >> n >> m;int M = 1LL << m;vector<PII> hou(m);vector<vector<int>> vis(n + 1, vector<int>(n + 1, -1));for (int i = 0; i < m; i++) {cin >> hou[i].first >> hou[i].second;vis[hou[i].first][hou[i].second] = i;}vector<vector<vector<int>>> g(n + 1, vector<vector<int>>(n + 1, vector<int>(M))), f = g;for (int sta = 0; sta < M; sta++) {for (int i = 0; i < m; i++) {if (sta >> i & 1) {for (int k = 0; k < 8; k++) {int x = hou[i].first + dx[k], y = hou[i].second + dy[k];if (x < 0 || x > n || y < 0 || y > n) continue;int cx = hou[i].first + dx_[k / 2], cy = hou[i].second + dy_[k / 2];if (cx < 0 || cx > n || cy < 0 || cy > n) {g[x][y][sta] = 1;continue;}int id = vis[cx][cy];if (id != -1 && (sta >> id & 1)) {continue;}g[x][y][sta] = 1;}}}}if (g[0][0][M - 1]) f[0][0][M - 1] = 0;else f[0][0][M - 1] = 1;for (int i = 0; i <= n; i++) {for (int j = 0; j <= n; j++) {if (i == 0 && j == 0) continue;for (int sta = 0; sta < M; sta++) {if (vis[i][j] == -1) {int num1 = 0, num2 = 0;if (i > 0) num1 = f[i - 1][j][sta];if (j > 0) num2 = f[i][j - 1][sta];if (!g[i][j][sta]) f[i][j][sta] = (num1 + num2) % mod;else f[i][j][sta] = 0;} else {int id = vis[i][j];if (!(sta >> id & 1)) continue;int num1 = 0, num2 = 0;if (i > 0) num1 = f[i - 1][j][sta];if (j > 0) num2 = f[i][j - 1][sta];if (!g[i][j][sta ^ (1 << id)]) f[i][j][sta ^ (1 << id)] = (num1 + num2) % mod;else f[i][j][sta ^ (1 << id)] = 0;}}}}   int ans = 0;for (int i = 0; i < M; i++) {if (!g[n][n][i]) {(ans += f[n][n][i] % mod) %= mod;}}cout << ans << endl;
}