Submission #27771931

---

Source Code Expand

# 解説を読んでも理解できず困っていたけど、最近のABCに類題
# https://atcoder.jp/contests/abc228/tasks/abc228_g
# が出て、この解説（解説放送）で理解できた！　ありがとう！

H,W=map(int,input().split())
mod=998244353

E=dict()

def dfs(X,s):
    ANS={X}

    if s==H:
        return ANS

    ANS|=dfs(tuple(X),s+1)

    X=list(X)

    if X[s]==0 and X[s+H]==0:
        X[s]=1
        X[s+H]=1
        ANS|=dfs(tuple(X),s+1)
        X[s]=0
        X[s+H]=0

    if s<H-1 and X[s]==0 and X[s+1]==0:
        X[s]=1
        X[s+1]=1
        ANS|=dfs(tuple(X),s+2)
        X[s]=0
        X[s+1]=0

    X=tuple(X)

    return ANS
    
NOW=tuple([0]*H)
Q=[(NOW,)]

while Q:
    e1=Q.pop()
    if e1 in E:
        continue
    L=set()

    for e in e1:
        L|=dfs(tuple(e)+(0,)*H,0)

    D=dict()

    for l in L:
        x=l[:H]
        y=l[H:]

        if x in D:
            D[x].append(y)
        else:
            D[x]=[y]

    for x in D:
        D[x].sort()
        if e1 in E:
            E[e1].append(tuple(D[x]))
        else:
            E[e1]=[tuple(D[x])]
            
        if tuple(D[x]) in E:
            continue
        else:
            Q.append(tuple(D[x]))

LIST=list(E)
DP=[0]*len(E)
DP[0]=1
DICT=dict()
for i in range(len(LIST)):
    DICT[LIST[i]]=i

X=[]
for i in range(len(LIST)):
    Y=[0]*len(LIST)
    for to in E[LIST[i]]:
        Y[DICT[to]]+=1
    X.append(Y)


# 行列の計算（numpyを使えないとき,modを使用）
def prod(A,B,k,l,m):# A:k*l,B:l*m
    C=[[None for i in range(m)] for j in range(k)]

    for i in range(k):
        for j in range(m):
            ANS=0
            for pl in range(l):
                ANS=(ANS+A[i][pl]*B[pl][j])%mod

            C[i][j]=ANS

    return C

def plus(A,B,k,l):# a,B:k*l
    C=[[None for i in range(l)] for j in range(k)]

    for i in range(k):
        for j in range(l):
            C[i][j]=(A[i][j]+B[i][j])%mod

    return C

# 漸化式を行列累乗で求める（ダブリング）

POWA=[X]
LEN=len(E)

for i in range(60):
    POWA.append(prod(POWA[-1],POWA[-1],LEN,LEN,LEN)) # ベキを求めて

X=[0]*LEN
X[0]=1
X=[X]

n=W-1

while n:
    X=prod(X,POWA[n.bit_length()-1],1,LEN,LEN) # n乗の場合
    n-=1<<(n.bit_length()-1)

DP=X[0]

def dfslast(X,s):
    ANS={X}

    if s==H:
        return ANS

    X=list(X)

    ANS|=dfslast(tuple(X),s+1)

    if s<H-1 and X[s]==0 and X[s+1]==0:
        X[s]=1
        X[s+1]=1

        ANS|=dfslast(tuple(X),s+2)
        X[s]=0
        X[s+1]=0

    X=tuple(X)

    return ANS

LANS=0
for i in range(len(E)):
    L=LIST[i]
    XX=set()
    for l in L:
        XX|=dfslast(l,0)

    LANS+=DP[i]*len(XX)

print(LANS%mod)

Submission Info

Judge Result