区切りは板チョコのように、行・列とも一直線に端から端まで入る。(明治のTHE・チョコレートは例外)
区切るべき区画の個数は、初期盤面にある 'Y' の個数で一意に決まる。
'Y' が奇数個なら不可能。偶数個なら、$2n$ とすると、$n$ 個の区画に分けることになる。
行方向に区切る数、列方向に区切る数をそれぞれ $R,C$ とすると、$n=RC$ なので、
$(R,C)$ の組は $n$ を2整数の積に分ける方法の数に限定される。
さらに $H \ge R,W \ge C$ という制約もある。
この $(R,C)$ を全探索する。
$R,C$ を固定した時にどうなっていればいいかというと、'Y' の個数の2次元累積和を取ったときに
: : : :
... 2 ... 4 ... 6 ... ...2C
: : : :
... 4 ... 8 .. 12 ... .. 4C
: : : :
: : : :
...2R .. 4R .. 6R ... ..2RC
このような条件を満たす $n$ 個のマスが存在していればよいことになる。
これらの各マスのすぐ右・すぐ下に区切りを入れることで、全ての区画の'Y'を2個ずつにできる。
途中の行・列はどこでもよいのだが、最終行・最終列は必ず使わなければならない点に注意。
ここで面倒なのが、上の条件を満たすマスの配置は複数出てきてしまうことがあり、
それらは別の区切り方として数えなければならない点。
累積和の $i$ 行目の $j_1,j_2,...$ 列目を拾うと $2k,4k,...,2Ck$ の並びが現れるとする。
また、$i+1$ 行目でも同じ列を拾うと、同じ$2k,4k,...,2Ck$ の並びが現れるとする。
この時、グリッドの $i+1$ 行目は全て 'X' となっているはずである。
$i$ 行目の直後に区切りを入れるのと、$i+1$ 行目の直後に入れるのとの違いで、全体の可能不可能に影響はもたらさない。
よって、最初に全て 'X' である行・列を除いてやれば、$(R,C)$ を固定した時の $n$ 個のマスは必ず一意に定まる。
少なくとも最終行・最終列が続けて同じ数ということが無くなるので、
最終行で $2R,4R,...,2RC$、最終列で $2C,4C,...,2RC$ の並びが現れる位置をそれぞれ調べ、
現れるなら、他の箇所も満たされるか調べればよい。
除いた盤面で、ある行の直後に区切りを入れることになった場合、元の盤面に戻って区切りを実際に入れる箇所の候補は、
「自身、および自身から次に除かない行が出てくるまでに除いた行」の直後となる。
... 2k ... 4k ..... 2Ck __ ←除いた盤面でのこの行における
(除) ... 2k ... 4k ..... 2Ck __ 元の盤面での区切り位置候補は3箇所
(除) ... 2k ... 4k ..... 2Ck __
... 2k ..4k+1 ... 2Ck+5
この候補は、区切りを入れる位置に対してそれぞれ独立に存在する。
よって一意に定まった区切り位置に対して、各位置の候補数の積が、$(R,C)$ を決め打ったときの答えとなる。
(※最終行・最終列に関しては候補数は1固定である点に注意)
前処理に $O(HW)$、その後1回の $(R,C)$ の決め打ちで $n$ 個(最大 $HW/2$)のマスを参照することになるが、
$n$ が最大に近いなら、$H \ge R,W \ge C$ という制約のため、$(R,C)$ の候補は多くない
$n$ が小~中程度なら、$(R,C)$ の候補は多少増えうるが、1回の探索にかかる負担は少ない
ため、正確な計算量解析は難しいが、2秒あれば十分通る計算量となる。
Python3
def compress_row(field):
free = [1]
new_field = []
for row in field:
if all(c == 'X' for c in row):
free[-1] += 1
else:
new_field.append(row)
free.append(1)
return new_field, free[1:]
def check1(acc2d, n, m, a, b):
row_step = b * 2
col_step = a * 2
row_idx = []
tgt = row_step
for i in range(n):
if tgt == acc2d[i][-1]:
row_idx.append(i)
tgt += row_step
elif tgt < acc2d[i][-1]:
return None
col_idx = []
tgt = col_step
for j in range(m):
if tgt == acc2d[-1][j]:
col_idx.append(j)
tgt += col_step
elif tgt < acc2d[-1][j]:
return None
return row_idx, col_idx
def check2(acc2d, a, b, row_idx, col_idx):
for ri in range(a):
i = row_idx[ri]
for ci in range(b):
j = col_idx[ci]
if acc2d[i][j] != (ri + 1) * (ci + 1) * 2:
return False
return True
def solve(h, w, field):
MOD = 998244353
field, free_row = compress_row(field)
field, free_col = compress_row(zip(*field))
field = list(zip(*field))
n = len(field)
if n == 0:
return 0
m = len(field[0])
acc2d = [[0] * m for _ in range(n)]
acc2d[0][0] = int(field[0][0] == 'Y')
for i in range(1, n):
acc2d[i][0] = acc2d[i - 1][0] + (field[i][0] == 'Y')
for j in range(1, m):
acc2d[0][j] = acc2d[0][j - 1] + (field[0][j] == 'Y')
for i in range(1, n):
for j in range(1, m):
acc2d[i][j] = acc2d[i - 1][j] + acc2d[i][j - 1] - acc2d[i - 1][j - 1] + (field[i][j] == 'Y')
total = acc2d[-1][-1]
if total % 2 == 1:
return 0
half = total // 2
pairs = []
for a in range(1, h + 1):
if half % a == 0 and half // a <= w:
pairs.append((a, half // a))
ans = 0
for a, b in pairs:
result = check1(acc2d, n, m, a, b)
if result is None:
continue
row_idx, col_idx = result
if check2(acc2d, a, b, row_idx, col_idx):
tmp = 1
for i in row_idx[:-1]:
tmp *= free_row[i]
tmp %= MOD
for j in col_idx[:-1]:
tmp *= free_col[j]
tmp %= MOD
ans += tmp
ans %= MOD
return ans
h, w = map(int, input().split())
field = [input() for _ in range(h)]
ans = solve(h, w, field)
print(ans)