POJ 3254 압축 상태 DP

제목: 직사각형 격자로 0 또는 1을 채울 수 있지만 어떤 위치는 아무 것도 채울 수 없습니다. 두 개의 격자가 동시에 1이 아니라 몇 가지 채울 수 있는지 요구합니다.직사각형 크기 최대 12*12.
압축 상태 DP는 대부분 실행 가능한state의 범위를 가지고 있습니다. 우선이state범위를 구하면 다음 문제를 푸는 데 매우 도움이 됩니다!
특판 N=1의 상황을 주의해라.

#include <iostream>

#include <cmath>

#include <cstring>

#include <vector>

using namespace std;

vector<int> t;  // the current map

vector<int> s;  // possible state

int MOD = 100000000;

int dp[15][1<<15];

int main()

{

    //freopen("1.txt","r",stdin);

    int M,N;

    while(cin>>M>>N)

    {

        s.clear(); t.clear();

        for(int tag=0; tag< (1<<N); tag++)

        {

            for(int k=0; k<N-1; k++)

            {

                if((tag &(1<<k)) && (tag &(1<<(k+1)))) break;

                if( k== N-2) s.push_back(tag);

            }

        }

        if(N == 1) {s.push_back(0); s.push_back(1);}

        for(int i=0; i<M; i++)

        {

            int x = 0;

            for(int j=0; j<N; j++)

            {

                int tag; cin>>tag;

                x += tag<<(N - j -1);

            }

            t.push_back(x);

        }



        memset(dp, 0, sizeof(dp));

        for(int i=0; i<s.size(); i++) 

        {

            if((s[i] | t[0]) ^ t[0]) continue;

            dp[0][s[i]] = 1;

        }

        for(int i=1; i< M; i++)   // row i

        {

            for(int j=0; j<s.size(); j++)

            {

                if((s[j] | t[i]) ^ t[i]) continue;

                //cout<<"Possible" <<s[j]<<endl;

                // cur state is s[j], pre is s[k];

                for(int k=0; k<s.size(); k++)

                {

                    if(s[j] & s[k]) continue;

                    dp[i][s[j]] += dp[i-1][s[k]];

                    dp[i][s[j]] %= MOD;

                }

            }

        }

        int ret = 0;

        for(int i=0; i<s.size(); i++)

        {

            ret += dp[M-1][s[i]];

            ret %= MOD;

        }

        cout<<ret<<endl;

    }

    return 0;

}

.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, "Courier New", courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }