Submission #19422747


Source Code Expand

Copy
import sys
readline = sys.stdin.readline

MOD = 10**9+7
H, W = map(int, readline().split())

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
Task S - マス目
User Tallfall
Language PyPy3 (7.3.0)
Score 7
Code Size 3805 Byte
Status AC
Exec Time 423 ms
Memory 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