ABC248 F - Keep Connect

atcoder.jp

【問題】
格子状のグラフが与えられ、i本辺を削った際に連結であるものの数。

【回答の考え方】
左から順番に、辺を取り除いた場合、辺を取り除かなかった場合に対してDPを行う。
辺を取り除く制約として、すでに2頂点が連結済みかどうか考慮する必要がある為、
それぞれ場合分けしながらDPを行う。

n,mod=map(int,input().split())

renketsu=[[0]*(n+4) for _ in range(n)]
mi_renketsu=[[0]*(n+4) for _ in range(n)]

for i in range(n):
    #左からi個目の頂点を考える
    if i==0:
        #上も下も連結するためには、上と下を結ぶ必要があるので
        #左からi番目の辺を削ることはできない

        #上と下を未連結にするためには辺を一つ削れば良い
        renketsu[i][0]=1
        mi_renketsu[i][1]=1

    else:
        #連結に対してのパターンは8通り

        #悲連結に対してのパターンは2通り
        #合計j本削る
        for j in range(n):

            mi_renketsu[i][j+1]+=mi_renketsu[i-1][j]%mod
            renketsu[i][j]+=mi_renketsu[i-1][j]%mod

            mi_renketsu[i][j+2]+=renketsu[i-1][j]%mod
            renketsu[i][j+1]+=renketsu[i-1][j]%mod
            renketsu[i][j]+=renketsu[i-1][j]%mod

            mi_renketsu[i][j+2]+=renketsu[i-1][j]%mod

            renketsu[i][j+1]+=renketsu[i-1][j]%mod
            renketsu[i][j+1]+=renketsu[i-1][j]%mod
#print("renketsu")
#for item in renketsu:
#    print(item)
#print("mi_renketsu")
#for item in mi_renketsu:
#    print(item)

for i in range(1,n):
    print(renketsu[-1][i]%mod)