【題解】ZeroJudge a228: 就少一個插座用很不方便

#include <bits/stdc++.h>
using namespace std;

int t, n, m, g[12][12], dp[12][12][1<<12], mod = 1e9+7;

int main(){
    cin >> t;
    for (int Case = 1; Case <= t; Case++){
        cin >> n >> m;
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++){
                cin >> g[i][j];
            }
        }
        memset(dp, 0, sizeof(dp));
        dp[0][m][0] = 1;
        for (int i = 1; i <= n; i++){
            for (int j = 0; j < (1<<m); j++){
                dp[i][0][j<<1] = dp[i-1][m][j];
            }
            for (int j = 1; j <= m; j++){
                int x = (1<<(j-1));
                int y = (1<<j);
                if (g[i][j] == 0){
                    for (int s = 0; s < (1<<(m+1)); s++){
                        if ((s&x) || (s&y)){
                            dp[i][j][s] = 0;
                        }
                        else dp[i][j][s] = dp[i][j-1][s];
                    }
                }
                else{
                    for (int s = 0; s < (1<<(m+1)); s++){
                        dp[i][j][s] = dp[i][j-1][s^x^y];
                        if (!!(s&x) != !!(s&y)) dp[i][j][s] += dp[i][j-1][s];
                        dp[i][j][s] %= mod;
                    }
                }
            }
        }
        cout << "Case " << Case << ": " << dp[n][m][0] << "\n";
    }
}