SRM 514 Div1 Medium MagicalGirlLevelTwoDivOne

落ち着いてたら本番で解けてた。。。

問題

hxwマスの長方形の板がある。それぞれのマスには1-9の数字または'.'が書かれている。


i行j列目の数をf[i][j]とするとき、
任意の0≦i≦h-nについて、

  • f[i][j]+f[i][j+1]+f[i][j+2]+…+f[i][j+n-1]が奇数

任意の0≦j≦w-mについて、

  • f[i][j]+f[i+1][j]+f[i+2][j]+…+f[i+m-1][j]が奇数


となるように'.'を埋める場合の数はいくつか。mod1000000007で求めよ。

制約条件

h,w≦50
n,m≦10

方針

偶奇はnxmの長方形を敷き詰めたようになる。
すなわちf[i][j]≡f[i+n][j+m] (mod 2)が成り立つ。


そこで、nxmマスの長方形に情報をまとめて処理する。
具体的には各マスにまとめられるような'.'がいくつあるか、偶数の数があるか、奇数の数があるか。


その後、dp[i][j]を、
i行目までで、各列の和の余りがjのそれぞれのビットに対応するような場合の数として、
それを更新するようなdpをする。

ソースコード

const int mod=1000000007;
ll dp[11][1<<10];
int num[50][50];
ll four[2501],five[2501];

class MagicalGirlLevelTwoDivOne {
public:
  int theCount(vector <string> palette, int n, int m) {
  	int h=palette.size(), w=palette[0].size();
  	int odd[10][10]={},even[10][10]={},dot[10][10]={};

  	four[0]=five[0]=1;
  	rep(i,2500){
  		four[i+1]=(four[i]*4)%mod;
  		five[i+1]=(five[i]*5)%mod;
  	}
  	
  	rep(i,h)rep(j,w){
  		num[i][j]=palette[i][j]=='.'?-1:palette[i][j]-'0';
  		
  		if(num[i][j]<0)dot[i%n][j%m]++;
  		else if(num[i][j]%2)odd[i%n][j%m]=1;
  		else even[i%n][j%m]=1;
  	}
  	
  	rep(i,n+1)rep(j,1<<m)dp[i][j]=0;
  	dp[0][0]=1;
  	
  	rep(i,n)rep(j,1<<m)if(dp[i][j])rep(k,1<<m){
  		
  		if(__builtin_popcount(k)%2==0)continue;
  		//次の列の状態はk。列の和は奇数でなければならない。
  		
  		ll ptn=1;
  		rep(l,m){
  			if(k&1<<l){
  				if(even[i][l]){
  					ptn=0; break;
  				}
  				ptn*=five[dot[i][l]];
  			}
  			else{
  				if(odd[i][l]){
  					ptn=0; break;
  				}
  				ptn*=four[dot[i][l]];
  			}
  			ptn%=mod;
  		}
  		dp[i+1][j^k]=(dp[i+1][j^k]+dp[i][j]*ptn)%mod;
  		//今までの和がjなので、各ビットにkを足すとj^kになる
  	}
  	
  	return dp[n][(1<<m)-1];
  }
};