• 知識點：線性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;
}