Submission #41281946

---

Source Code Expand

import sys
def input():
    return sys.stdin.readline().rstrip()
# Typical DP Contest M - 家
# R <=16なのでダブリング(10**9)*2**16で計算量は1966080になる
# どこから降りるか
# 最後は1から降りることになる
# (2**16)*30*16*16=503316480 間に合いそう
H, R = map(int, input().split())
G = [list(map(int, input().split())) for i in range(R)]
MOD = 10**9+7
#dp[i] 今いるフロアを含めて2**iフロア移動するとき、出発するフロアのjから到着するフロアのkに移動する場合の数

# フロアをまたがないsからtへの移動経路数 巡回セールスマン
dp_sum = [[0]*R for _ in range(R)]
for r in range(R):
    dp_sum[r][r] = 1
for s in range(R):
    # 初期化
    dp = [[0]*R for _ in range(1<<R)]
    dp[1<<s][s] = 1
    # dp[S][i]の値を順に求めていく
    # すでに訪問した都市の集合を表す整数がSで、最後に訪れた都市がiであるような状態に至る経路数
    for S in range(1<<R):
        for i in range(R):
            #未訪問の場合スキップ
            if S & (1 << i) == 0:continue
            # 都市 jで場合分け jからiに来る
            for j in range(R):
                if j == i or S & (1 << j) == 0:continue
                if G[j][i] == 0:continue
                # 更新 Sで表される都市の集合都市vをのぞいてできる集合
                dp[S][i] += dp[S & ~(1 << i)][j]
                dp[S][i] %= MOD
    for d in dp:
        for t in range(R):
            if s == t: continue
            dp_sum[s][t] += d[t]
            dp_sum[s][t] %= MOD
# print(dp_sum)
# dp[i][j][k]jから2**i回移動するとkにいる数
L = len(bin(H)[2:])#bit長
dp = [[[0]*R for i in range(R)] for _ in range(L)]
# 初期化
for i in range(R):
    for j in range(R):
        dp[0][i][j] = dp_sum[i][j]
for i in range(L-1):
    for j in range(R):
        for k in range(R):
            for l in range(R):
                # jからkに移動
                dp[i+1][j][k] = (dp[i+1][j][k]+dp[i][j][l]*dp[i][l][k])%MOD
#2進数表記の逆順
S = bin(H)[2:][::-1]
prev = [0]*R 
prev[0] = 1
for i in range(L):
    if S[i] == "0":continue
    cur = [0]*R
    # jにいる場合の数とjからkに移動する数を掛け合わせる
    for j in range(R):
        for k in range(R):
            cur[k] += prev[j]*dp[i][j][k]
            cur[k] %= MOD
    prev = cur
print(prev[0]%MOD)

Submission Info

Judge Result