AtCoder ABC #228 (トヨタシステムズプログラミングコンテスト2021) : G - Digits on Grid

久々に良い結果。(なお翌日のARCは…)
https://atcoder.jp/contests/abc228/tasks/abc228_g

問題

1～9の数字で埋まったH*Wのグリッドが与えられる。
ここで、まず先手が任意のセルに駒を置く。
以降、以下の手順をN周繰り返し、2N桁の整数を作る。

• 駒を現在位置と同じ行のうち任意の列に移動し、そのセルの数字を整数の末尾の桁に追加する。
• その後、駒を現在位置と同じ列のうち任意の行に移動し、そのセルの数字を整数の末尾の桁に追加する。

作れる整数は何通りか。

解法

同じ整数を作る手順に対し、駒の移動履歴が複数あるのがややこしい。
H,Wが小さいこと、各手順では列か行の片方だけ固定されることを用いて、以下のように処理する。

f(n,rmask) := 先頭2n桁を定めたとき、駒が存在しうる行の集合がrmaskであるような整数の組み合わせ
g(n,cmask) := 先頭(2n+1)桁を定めたとき、駒が存在しうる列の集合がcmaskであるような整数の組み合わせ

とする。
各状態において、次1～9を追加しようとしたとき、遷移できる列・行をどうできるか考えると、
f(0,(2^H-1))→g(0,*)→f(1,*)→g(1,*)→…→f(n,*)
と順に求めて行くことができる。

int H,W,N;
string S[10];
const ll mo=998244353;

ll A[1<<10];
ll B[1<<10];
ll C[1<<10];


vector<int> FA[1<<10];
vector<int> FB[1<<10];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>N;
	FOR(y,H) {
		cin>>S[y];
		FORR(c,S[y]) c-='1';
	}
	
	int mask;
	FOR(mask,1<<10) if(mask) {
		FOR(i,9) {
			int to=0;
			FOR(y,H) if(mask&(1<<y)) {
				FOR(x,W) if(S[y][x]==i) to|=1<<x;
			}
			FA[mask].push_back(to);
		}
		FOR(i,9) {
			int to=0;
			FOR(x,W) if(mask&(1<<x)) {
				FOR(y,H) if(S[y][x]==i) to|=1<<y;
			}
			FB[mask].push_back(to);
		}
		
	}
	
	A[(1<<H)-1]=1;
	while(N--) {
		int mask;
		ZERO(B);
		ZERO(C);
		FOR(mask,1<<10) FORR(t,FA[mask]) (B[t]+=A[mask])%=mo;
		FOR(mask,1<<10) FORR(t,FB[mask]) (C[t]+=B[mask])%=mo;
		swap(C,A);
	}
	ll ret=0;
	FOR(mask,1<<10) if(mask) ret+=A[mask];
	cout<<ret%mo<<endl;
	
}

まとめ

こちらは割とすぐに思いつけたものの、変なミスをして手間取ってしまった。