Contest Duration: - (local time) (300 minutes) Back to Home

Submission #19422747

Source Code Expand

Copy
```import sys

MOD = 10**9+7

K = 3
def zti(z):
res = 0
for zi in z:
res *= K
res += zi
return res
def itz(i):
res = []
for _ in range(H):
res.append(i%K)
i //= K
return res[::-1]
def check(z):
for zi, zj in zip(z, z[1:]):
if zi and zj and zi != zj:
return False
if zi >= 2 and z.count(zi) == 1:
return False
return True

Di = dict()
cnt = 0
D = []
for i in range(K**H):
s = itz(i)
if 1 in s and check(s):
Di[i] = cnt
cnt += 1
D.append(i)

class UF():
def __init__(self, col):
self.par = [-1]*len(col)
self.col = col
for i in range(len(col)):
for j in range(i):
if col[i] and col[i] == col[j]:
self.union(i, j)
def find(self, x):
if self.par[x] < 0:
return x
else:
stack = []
while self.par[x] >= 0:
stack.append(x)
x = self.par[x]
for xi in stack:
self.par[xi] = x
return x

def union(self, x, y):
rx = self.find(x)
ry = self.find(y)
if rx != ry:
if self.par[rx] > self.par[ry]:
rx, ry = ry, rx
self.par[rx] += self.par[ry]
self.par[ry] = rx
if not self.col[rx]:
res = self.col[ry]
elif self.col[ry]:
res = min(self.col[rx], self.col[ry])
else:
res = self.col[rx]
self.col[rx] = res
return rx

def compress(L):
L2 = list(set(L))
L2.sort()
C = {v : k for k, v in enumerate(L2)}
return L2, C

Edge = [[0]*cnt for _ in range(cnt)]
for idx in range(cnt):
i = D[idx]
for S in range(1<<H):
T = UF(itz(i))
for j in range(H-1):
if (1<<j)&S and (1<<j+1)&S:
T.union(j, j+1)
res = [None]*H
cc = 10
for j in range(H):
if not (1<<j)&S:
res[j] = 0
else:
c = T.col[T.find(j)]
if c:
res[j] = c
else:
res[j] = cc
T.col[T.find(j)] = cc
cc += 1
#print(1, itz(D[idx]), format(S, 'b').zfill(H)[::-1], res)
if 1 not in res:
continue
for k in range(H):
r = res[k]
if r >= 2 and res.count(r) == 1:
res[k] = 0
_, Cd = compress(res + [0])
res = [Cd[r] for r in res]

ri = zti(res)
if ri not in Di:
continue
Edge[Di[ri]][idx] += 1

def mat_dot(A, B):
assert len(A[0]) == len(B), 'invalid_size'

L = len(A)
M = len(A[0])
N = len(B[0])

res = [[0]*N for _ in range(L)]

for i in range(L):
for j in range(N):
a = 0
for k in range(M):
a = (a+A[i][k]*B[k][j]) % MOD
res[i][j] = a

return res

def mat_pow(A, x):
N = len(A)
res = [[0]*N for _ in range(N)]
for i in range(N):
res[i][i] = 1
for i in range(x.bit_length()):
if 2**i & x:
res = mat_dot(res, A)
A = mat_dot(A, A)
return res

dp = [0]*cnt
dp[Di[zti(tuple([1] + [0]*(H-1)))]] = 1
dp = mat_dot(mat_pow(Edge, W), [[d] for d in dp])

ans = 0
for idx in range(cnt):
if itz(D[idx])[-1] == 1:
ans = (ans + dp[idx][0])%MOD

print(ans)

```

#### Submission Info

Submission Time 2021-01-14 09:54:54+0900 S - マス目 Tallfall PyPy3 (7.3.0) 7 3805 Byte AC 423 ms 71508 KB

#### Judge Result

Set Name All
Score / Max Score 7 / 7
Status
 AC × 8
Set Name Test Cases
All 00, 01, 02, 03, 04, 05, 90, 91
Case Name Status Exec Time Memory
00 AC 423 ms 70744 KB
01 AC 376 ms 71508 KB
02 AC 164 ms 69716 KB
03 AC 81 ms 68156 KB
04 AC 64 ms 67624 KB
05 AC 56 ms 62808 KB
90 AC 58 ms 62756 KB
91 AC 163 ms 69300 KB