#include #include #include #include #include #include using namespace std; typedef long long lint; typedef vectorvi; typedef pairpii; #define rep(i,n)for(int i=0;i<(int)(n);++i) //参考 https://atcoder.jp/contests/tdpc/submissions/3921962 #define PRINT 0 const lint mo=998244353; const int LIM = 6; const int LOG_BASE = 4; int W,N; using Key=lint; mapcache[1<tovi(Key key){ vi a(W); rep(z,W){ a[z] = (int)((key >> (z * LOG_BASE)) & ((1 << LOG_BASE) - 1)); } int b=key>>(LOG_BASE*W); return make_pair(a,b); } Key tokey(vi a,int b){ // encode Key keyNext=0; assert(a.size()==W); rep(z,W){ assert(a[z]<2*W); keyNext |= (Key)(a[z]) << (z * LOG_BASE); } return keyNext|lint(b)<<(LOG_BASE*W); } void unify(vi&a,int x,int y){ int oldx=a[x],oldy=a[y]; assert(oldx/(2*W)==oldy/(2*W)); int to=min(oldx,oldy); rep(i,a.size())if(a[i]==oldx||a[i]==oldy)a[i]=to; } Key trans(Key key,int pat) { if(cache[pat].count(key))return cache[pat][key]; // decode auto ab = tovi(key); vi a; int b; tie(a,b)=ab; vi chu(2*W); int bl=0,wh=2*W+1; rep(i,W){ chu[i]=a[i]0&&bl==0&&pat>0)return cache[pat][key]=-1; rep(i,W)chu[i+W]=(pat&1<=2*W)chu[W]=2*W; if(chu[2*W-1]>=2*W)chu[2*W-1]=2*W; rep(j,2)rep(i,W-1)if(chu[j*W+i]/(2*W)==chu[j*W+i+1]/(2*W))unify(chu,j*W+i,j*W+i+1); rep(i,W)if(chu[i]/(2*W)==chu[i+W]/(2*W))unify(chu,i,i+W); //繋がらないことが確定した白がある? settop; rep(i,W)if(chu[i+W]>2*W)top.insert(chu[i+W]); rep(i,W)if(chu[i]>2*W&&!top.count(chu[i]))return cache[pat][key]=-1; //繋がらないことが確定した黒がある? top.clear(); setlft; rep(i,W)if(chu[i+W]<2*W)top.insert(chu[i+W]); rep(i,W)if(chu[i]<2*W&&!top.count(chu[i]))lft.insert(chu[i]); if(pat>0&&lft.size())return cache[pat][key]=-1; if(pat==0&&lft.size()>1)return cache[pat][key]=-1; //新しい頂点の個数は? rep(i,W+1){ int c=0; rep(j,2)rep(k,2)c+=(i-k>=0&&i-k=2*W?wh++:bl++; } } assert(tr[2*W]==-1||tr[2*W]==W); rep(z,W){ c[z] = tr[c[z]]; assert(c[z]<2*W); } // encode Key keyNext=tokey(c,b); cache[pat][key]=keyNext; return keyNext; } int main(){ int r,c,n;cin>>r>>c>>n; W=c;N=n; lint ans=0; mapcrt; vi fst(W); rep(i,W){ fst[i]=W; } crt[tokey(fst,0)]=1; //一段多く。最後は 0 rep(i,r+1){ cerr<<"i="<