考察
行の左prefixと列の上prefixの長さをそのまま選ぶと、同じ完成グリッドを複数の選択で表せるため重複する。列prefixを可能な限り伸ばす標準形を考える。行 i の左から最初の0より前は行prefixで覆え、それ以降の1は列prefixで覆う必要がある。
上から行を処理し、maskのbit j を「列 j はここまで全行で1なので、列prefixを次行へ伸ばせる」とする。初期は全bitが1、dp[all]=1。現在行の実際のbit列 b を選んだ後は newmask=mask AND b。既にmaskのbitが0の列へ1を置くには、その列までの全マスが1で、行prefixで覆えることが必要十分である。
素朴には各maskから2^M個のbを試す。次の分類なら列方向の一回のsweepへまとめられる。bがmaskの部分集合なら、列ごとにbit1を残すか0へ落とす遷移で処理できる。それ以外は「maskで0だがbで1となる最も右の列 j」が一意に存在する。列0,…,jは全て1、それより右ではbはmaskの部分集合でなければならない。
各行の開始時の dp を保存し、work=dp とする。j=0,…,M−1 の順に、入力文字に許される選択で全maskを走査して次配列を作る。
0を置ける: next[mask & ~(1<<j)] += work[mask]
1を置ける、かつ maskのbit j=1: next[mask] += work[mask]
列0,…,jを全て1にできるなら:
maskのbit j=0 の全maskについて next[mask] += dp[mask]
work=next
最後の加算は新たなprefixケースの開始である。prefix内は全て1なのでold maskのbitは変わらず、未処理の後ろのbitもそのまま。必ず行開始時の dp から加え、既に遷移した work から加えない。後続sweepではmaskが0の位置に1を置けないため、jが最も右の新しい1である条件も保たれる。
prefixを全て1にできるかは、そこまで固定0がないかを一つのbooleanで更新する。各列の全mask走査を O(2^M) に抑え、全体 O(NM2^M)、空間 O(2^M)。全行後の全maskの和が答えであり、最終maskが0でも、既に列prefixが停止した合法グリッドなので除外しない。
持ち帰る典型は、同じ構成を持つ対象を標準形へ寄せ、残る候補を一意な境界で分類してsubset変換へまとめることである。
典型の発動条件
bitmask frontier DP
発動条件: 幅が小さい格子を行単位で処理し、将来に影響する境界だけを保持する。
各列が上から伸長可能かをmaskにする。
発動条件: 全maskからその部分集合への和が必要。
行遷移の多数の部分集合和をO(M2^M)で求める。
問題固有の要素
行・列prefixの長さの選び方は一意ではないが、完成グリッドの「列の最初の0まで」という最大の列prefixは一意に決まる。行の合法性はこの標準形で判定し、行遷移はmaskの外に置く最も右の1で排他的に分類する。
別の問題へ持ち帰る視点: 構成方法の数と完成対象の数を区別し、標準形と一意な境界を定義してからsubset変換へまとめる。
正当性
列prefixをその列の最初の0の直前まで伸ばす標準形を選べる。各行で行prefixの外にある1が全て上から伸びる列で覆われることが必要十分なので、maskと現在行bから合法性を判定し、次maskをmask AND bとしてよい。bがmaskの部分集合の場合と、maskで0だがbで1の最も右の列jを持つ場合は排他的かつ全てを覆う。後者はprefix全1と後ろのsubsetを一通りだけ処理する。列sweepの加算はこの分類に一致するため完成グリッドを一度ずつ数え、固定文字に許される選択だけを行うので入力との整合も保つ。
実装上の注意
- 初期maskは全1、最終解は全maskの総和。0のmaskも合法になり得る。
- 各列のnextを0で初期化し、0/1の許可を入力文字から決める。prefixケースは行開始時のdpから加える。
- prefixに固定0が一つでもあれば、その列以降のprefixケースは追加できない。法998244353で加算する。
復習の核
- 小格子の全?埋めと比較し、全0・全1、固定値が遷移を遮る行、M=1を確認する。
計算量と制約
時間
O(NM2^M)。各行でsubset zeta sweepとprefix別遷移を行う。
空間
O(2^M)。行DPをrollingする。
制約との対応
公式制約の確認範囲: Time limit: 4 sec; Memory limit: 1024 MiB; Constraints: N and M are integers.; 1 \le N,M \le 18; X is a grid with N rows and M columns consisting of 0, 1, and ?.
出典