-
Notifications
You must be signed in to change notification settings - Fork 0
/
w_numba.py
79 lines (65 loc) · 2.37 KB
/
w_numba.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import sys
import numpy as np
def main():
h, w = map(int, input().split())
s = np.array([[c == '.' for c in input()]
for _ in range(h)], dtype=np.bool8)
print(solve(s))
if __name__ == "__main__":
if sys.argv[-1] == 'ONLINE_JUDGE':
from numba.pycc import CC
def solve(s):
h, w = s.shape
mod = 10 ** 9 + 7
mask = (1 << (w + 1)) - 1
def collision(j, b):
return (j > 0 and b & 1
or j + 1 < w and (b >> (w - 2)) & 1
or (b >> (w - 1)) & 1
or j > 0 and (b >> w) & 1)
states = []
for i in range(w):
lis = [0]
for j in range(w + 1):
nex = []
t = (i + j - 1) % w
for k in lis:
nex.append(k << 1)
if not collision(t, k):
nex.append(k << 1 | 1)
lis = nex
states.append(lis)
indices = []
for st in states:
dic = {}
for i, b in enumerate(st):
dic[b] = i
indices.append(dic)
# indices = [{b: i for i, b in enumerate(st)} for st in states]
nexts = [[[indices[i - w + 1][st << 1 & mask],
indices[i - w + 1][(st << 1 | 1) & mask]
if not collision(i, st) else -1]
for st in states[i]] for i in range(w)]
dp = [0 for _ in states[0]]
dp[0] = 1
for i in range(h):
for j in range(w):
nex = [0 for _ in states[j - w + 1]]
for k, c in enumerate(dp):
for l in range(2):
nk = nexts[j][k][l]
if l == 0 or s[i][j] and nk != -1:
nex[nk] += c
if nex[nk] >= mod:
nex[nk] -= mod
dp = nex
res = 0
for i in dp:
res += i
return res % mod
cc = CC('my_module')
cc.export('solve', 'int64(boolean[:, :])')(solve)
cc.compile()
else:
from my_module import solve
main()