[AtCoder] [經典競程 90 題] 023 - Avoid War（★7）

題目連結:https://atcoder.jp/contests/typical90/tasks/typical90_w
題目大意:
給定一個 $H \times W$ 的棋盤，其中被標記為 # 的格子代表不能擺棋子。問有多少種方式可以在棋盤上擺一堆西洋棋的國王而不會造成至少一組國王可以立即攻擊到對方。

---

看完馬上想到大根蘿蔔，這種題明顯要狀態壓縮 DP，狀態大概可以是 $dp[x][y][\text{mask}]$ 代表在 $(x, y)$ 的時候 $\text{mask}$ 裡面那些位置是可以擺的，然後轉移就真的看這格要不要擺之類的。 但如果真的無腦這樣做的話，複雜度會是 $O(H \times W \times 2^W)$ ，明顯會跑太久，不過仔細想了想就可以感受到合法狀態數絕對沒有這麼多，因為放一個就會蓋掉周遭之類的。
所以對於這種情況一個好方法就是我們可以先花 $W \times 2^W$ 的時間預處理真正合法的狀態，接著就可以 $O(H \times W \times X)$ (其中 $X$ 是真正可能的合法的狀態數) DP 掉了。
不過因為我很爛，從以前就一直不知道該怎麼好好寫這種預處理 DP，只知道這樣是可行的，所以這題最後跑去看官解程式碼才終於學會寫程式。
官解同時也有稍微說明我上面的那個 $X$ 其實就是費式數列的某項，因為把蓋掉之後能再放的拿出來估一估差不多就會跟費式數列遞迴式一樣。

#include <bits/stdc++.h>
using namespace std;
static constexpr int C = 167761;
static constexpr int N = 24;
static constexpr int N2 = 1 << N;
static constexpr int MOD = 1'000'000'007;

inline int add(int a, int b) {
	return a + b >= MOD ? a + b - MOD : a + b;
}

string a[N];

unordered_map<int, pair<int, int>> mp[N];
int cnt[N], state[N][C];
int ban[4][N];

void precalc(int p, int d, int s, int m) {
	const int x = p / m, y = p % m;
	if (d == m + 1) {
		state[y][cnt[y]] = s;
		mp[y][s] = {cnt[y]++, ban[x][y]};
		return;
	}
	precalc(p + 1, d + 1, s, m);
	if (ban[x][y]) return;
	static int dx[] = {0, 0, 1, 1, 1, -1, -1, -1};
	static int dy[] = {1, -1, 0, 1, -1, 0, 1, -1};
	for (int _ = 0; _ < 8; ++_) {
		int nx = x + dx[_], ny = y + dy[_];
		if (0 > nx or nx >= 4) continue;
		if (0 > ny or ny >= m) continue;
		ban[nx][ny]++;
	}
	precalc(p + 1, d + 1, s | (1 << d), m);
	for (int _ = 0; _ < 8; ++_) {
		int nx = x + dx[_], ny = y + dy[_];
		if (0 > nx or nx >= 4) continue;
		if (0 > ny or ny >= m) continue;
		ban[nx][ny]--;
	}
}

int nxt[2][N][C];
int dp[N + 1][N][C];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m; cin >> n >> m;
	for (int i = 0; i < n; ++i)
		cin >> a[i];

	for (int i = 0; i < m; ++i) precalc(i, 0, 0, m);
	for (int i = 0; i < m; ++i) {
		const int ni = (i + 1) % m;
		for (int j = 0; j < cnt[i]; ++j) {
			nxt[0][i][j] = mp[ni][state[i][j] >> 1].first;
			if (mp[i][state[i][j]].second) nxt[1][i][j] = -1;
			else nxt[1][i][j] = mp[ni][(state[i][j] >> 1) | (1 << m)].first;
		}
	}

	dp[0][0][0] = 1;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			const int ni = i + (j == m - 1), nj = (j + 1) % m;
			for (int s = 0; s < cnt[j]; ++s) {
				for (int _ = 0; _ < 2; ++_) {
					if (nxt[_][j][s] == -1) continue;
					if (_ != 0 and a[i][j] != '.') continue;
					dp[ni][nj][nxt[_][j][s]] = add(dp[ni][nj][nxt[_][j][s]], dp[i][j][s]);
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < cnt[0]; ++i) ans = add(ans, dp[n][0][i]);
	cout << ans << '\n';
	return 0;
}