yukicoder : No.3285 Chorus with Friends

久々にこれ系のテクを使った。
https://yukicoder.me/problems/no/3285

問題

長さMの整数列がN個与えられる。
初期状態で、長さNの整数列F=(A[1][1],A[2][1],...,A[N][1])とする。

空の整数列Xに対し、計M回以下を行う。

• Fの1要素を選び、Xに追加する。もしi回目の処理でF[j]を選んだ場合、F[j]=A[j][i]で置き換える。

Xの全要素が同じになるような選択の仕方は何通りか。

解法

N*M≦300なので、N,Mの大小関係に応じて、BitDPを縦方向と横方向で切り替えながら行おう。
いずれも、Xに入れる最初の要素を総当たりで決め打ちする。

Nが小さい場合、Fの各要素のうち、Xの先頭要素と等しいかどうかを状態にもって時系列でBitDPする。
Mが小さい場合、数列の行ごとに、要素選択が回次ごとに未確定かどうかを状態にもってBitDPする。

int H,W;
int A[303][303];
const ll mo=998244353;
ll from[1<<17];
ll to[1<<17];
ll from2[1<<17][2][2];
ll to2[1<<17][2][2];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) FOR(x,W) cin>>A[y][x];
	
	if(W==1) {
		cout<<H<<endl;
		return;
	}
	if(H==1) {
		FOR(x,W) if(A[0][x]!=A[0][0]) {
			cout<<0<<endl;
			return;
		}
		cout<<1<<endl;
		return;
	}
	
	ll ret=0;
	int mask;
	if(H<=W) {
		FOR(i,H) {
			int v=A[i][0];
			ZERO(from);
			mask=0;
			FOR(y,H) if(i!=y&&A[y][0]==v) mask|=1<<y;
			if(A[i][1]==v) mask|=1<<i;
			from[mask]=1;
			for(x=2;x<W;x++) {
				ZERO(to);
				FOR(mask,1<<H) if(from[mask]) {
					FOR(y,H) if(mask&(1<<y)) {
						int nmask=mask^(1<<y);
						if(A[y][x]==v) nmask|=1<<y;
						(to[nmask]+=from[mask])%=mo;
					}
				}
				swap(from,to);
			}
			FOR(mask,1<<H) ret+=from[mask]*__builtin_popcount(mask)%mo;
		}
	}
	else {
		W-=2;
		FOR(i,H) {
			int v=A[i][0];
			ZERO(from2);
			from2[0][0][0]=1;
			FOR(y,H) {
				FOR(mask,1<<W) FOR(j,2) FOR(k,2) {
					to2[mask][j][k]=from2[mask][j][k];
					from2[mask][j][k]=0;
				}
				FOR(mask,1<<W) FOR(j,2) FOR(k,2) from2[mask][A[y][i==y]==v][k]+=to2[mask][j][k];
				FOR(x,W) {
					FOR(mask,1<<W) FOR(k,2) if((mask&(1<<x))==0) from2[mask^(1<<x)][A[y][x+2]==v][k]+=from2[mask][1][k];
				}
				FOR(mask,1<<W) FOR(j,2) FOR(k,2) {
					to2[mask][j][k]=from2[mask][j][k];
					from2[mask][j][k]=0;
				}
				FOR(mask,1<<W) {
					from2[mask][0][0]=(to2[mask][0][0]+to2[mask][1][0])%mo;
					from2[mask][0][1]=(to2[mask][1][0]+to2[mask][0][1]+to2[mask][1][1])%mo;
				}
			}
			ret+=from2[(1<<W)-1][0][1];
		}
	}
	
	cout<<ret%mo<<endl;

}

まとめ

H*Wの上限が一定で、HとWどちらが大きいかで処理を分けるの、SRMでしばしば見た気がする。