提出 #17308590

---

ソースコード 拡げる

import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 1_000_000_007

@njit((i8[:, :], ), cache=True)
def main(wall):
    cnt = np.zeros_like(wall)
    for _ in range(4):
        cnt, wall = cnt[::-1].T, wall[::-1].T
        A = np.zeros_like(cnt)
        # 上にあるものを数える。自身は含まない
        H, W = A.shape
        for h in range(1, H):
            x = A[h - 1] + 1
            x *= (1 - wall[h - 1])
            A[h] = x
        cnt += A
    cnt = (1 + cnt) * (1 - wall)
    H, W = cnt.shape
    pow2 = np.ones(H * W + 10, np.int64)
    for i in range(H * W + 9):
        pow2[i + 1] = pow2[i] * 2 % MOD
    ans = 0
    K = (1 - wall).sum()
    for n in cnt.ravel():
        if n == 0:
            continue
        ans += pow2[K] - pow2[K - n]
    return ans % MOD

H, W = map(int, readline().split())
S = np.frombuffer(read(), 'S1').reshape(H, -1)[:, :W]

wall = ((S == b'#') * 1).astype(np.int64)
print(main(wall))

提出情報

ジャッジ結果