POJ 3254 Corn Fields：狀壓 DP 解決放牛問題

POJ 3254 Corn Fields：狀壓 DP 解決放牛問題

n 行 m 列草地（m≤12），1 表可放牧，0 不可。牛放在可放牧格，且任兩牛不可相鄰（上下左右）。求放牛方案數模 1e8。

狀態壓縮

每行狀態用 m 位二進制數表示：1=放牛，0=不放。合法狀態滿足：

1. 無相鄰 1：(s & (s<<1)) == 0。
2. 僅在可放牧格：(s & ~grass_row) == 0，即 (s & forbidden) == 0。輸入 1=可放，取反得 forbidden。

預計算所有合法狀態存入 status[]，數量 ≤ F_{m+2} (m=12 時 377)。

DP 轉移

dp[i][s] = 前 i 行，第 i 行狀態為 s 的方案數。轉移：

for (int i=1; i

const int MOD = 100000000;
int grass[15], status[1<<12], dp[15][1<<12];

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) == 2) {
        memset(grass, 0, sizeof(grass));
        for (int i=0; i