SRM514 Div1 Medium(600) MagicalGirlLevelTwoDivOne

MagicalGirlLevelTwoDivOne

石版の数字の偶奇に着目すると、高さn幅mの長方形の繰り返しになっている。0≦i＜nと0≦j＜2^mについて、y=i+kn行の偶奇がjになるような数字の置き方の数を求めておく。これを使って、全ての列が奇数個の奇数を含む数字の置き方を動的計画法で求める。

#include <string>
#include <vector>
using namespace std;

int countbit( int n ) { int c=0; while(n)c+=n&1,n>>=1; return c; }

class MagicalGirlLevelTwoDivOne{public:
int theCount( vector <string> palette, int n, int m )
{
    long long M = 1000000007;
    int H = (int)palette.size();
    int W = (int)palette[0].size();

    vector<vector<long long> > T( n, vector<long long>(1<<m) );
    for ( int i=0; i<n; i++ )
    for ( int j=0; j<1<<m; j++ )
    {
        if ( countbit(j)%2 == 0 )
        {
            T[i][j] = 0;
        }
        else
        {
            T[i][j] = 1;
            for ( int y=i; y<H; y+=n )
            for ( int x=0; x<W; x++ )
                if ( palette[y][x]=='.' )
                    T[i][j] *= 4 + (j>>(x%m)&1),
                    T[i][j] %= M;
                else if ( (palette[y][x]-'0')%2 != (j>>(x%m)&1) )
                    T[i][j] = 0;
        }
    }

    vector<vector<long long> > S( n, vector<long long>(1<<m) );
    for ( int i=0; i<1<<m; i++ )
        S[0][i] = T[0][i];
    for ( int i=1; i<n; i++ )
    for ( int j=0; j<1<<m; j++ )
    {
        S[i][j] = 0;
        for ( int k=0; k<1<<m; k++ )
            S[i][j] += S[i-1][j^k] * T[i][k],
            S[i][j] %= M;
    }

    return (int)S[n-1][(1<<m)-1];
}};