3118366_ac_0ms_436k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {

    int infertile[13] = {0};
    int dp[13][4096];
    int R, C, C2;
    vector<int> valid;

    cin >> R >> C;
    C2 = 1 << C;
    fill(infertile, infertile + R, 0);
    for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
            int x;
            cin >> x;
            if (!x) infertile[i + 1] |= 1 << j;
        }
	}
    for ( i = 0; i < C2; i++){
		if (!(i & (i << 1))) 
		{
			valid.push_back(i);
		}
	}
    fill(dp[0], dp[0] + C2, 1);
    for (i = 1; i <= R; i++)
	{
        fill(dp[i], dp[i] + C2, 0);
        for (int j = 0; j < C2; j++)
		{
            if (~j & infertile[i]) continue;
            for (size_t k = 0; k < valid.size(); k++)
			{
                int u = valid[k];
                if (u & j) continue;
                dp[i][j] += dp[i - 1][u | infertile[i - 1]];
                dp[i][j] %= 100000000;
            }
        }
    }
    cout << dp[R][infertile[R]] << "\n";
    return 0;
}