問題描述
M×N 塊地 (M,N≤12)，部分格子可種樹(1)、部分不可(0)。樹不能相鄰（上下左右）。求合法種植方案數模 100,000,000。
狀態定義與轉移
按行從下往上、每行從右往左處理。狀態 S (N 位) 表示已種完該行前 j 列的種植情況。對位置 (i,j)：
- 不可種地：
S[j]=0 強制，繼承上一狀態
- 可種地：
S[j]=0 來自 S'[j]=0；S[j]=1 要求 S'[j]=0 且左鄰 S[j-1]=0（若 j>0）
雙緩衝滾動數組 dp[2][1< 節省空間。
核心代碼
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 14, MOD = 100000000;
int land[MAXN][MAXN];
int dp[2][1<=0; i--)
for (int j=n-1; j>=0; j--) {
for (int used=0; used<1<>j & 1) nxt[used] = 0;
else {
nxt[used] = cur[used];
nxt[used] = (nxt[used] + cur[used | (1<>j & 1), left = (j+1>(j+1) & 1));
if (up && left) res = 0;
else if (!up && left) { res = cur[used]; res += cur[used | (1<
關鍵細節
- 狀態語義：「已種完」而非「將要種」，注意與多米諾骨牌問題區別
- 雙緩衝交換
swap(cur, nxt) 避免數組拷貝
- 模數操作及時進行防止溢出
- 最終答案為所有合法終止狀態之和
複雜度
- 狀態數：2^N ≤ 4096
- 轉移：M×N×2^N ≤ 12×12×4096 ≈ 6×10^5
- 極快通過
