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]; } };