#1173649 (PyPy3) No.3600 Moving Queen Many Times

• 問題: No.3600 Moving Queen Many Times
• ユーザー: LyricalMaestro
• 提出日時: 2026-07-25 16:25:36
• 言語: PyPy3 (7.3.17)
• 結果: AC
• 実行時間: 1,539 ms / 7,000 ms
• コード長: 4,022 bytes
• コンパイル時間: 423 ms
• コンパイル使用メモリ: 95,620 KB
• 実行使用メモリ: 316,800 KB
• 最終ジャッジ日時: 2026-07-25 16:25:59
• 合計ジャッジ時間: 20,523 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 75

ソースコード

# https://yukicoder.me/problems/no/3600

from collections import deque

MOD = 998244353

def same_line(h0, w0, h1, w1):
    if h0 == h1 or w0 == w1:
        return True
    elif h0 - w0 == h1 - w1:
        return True
    elif h0 + w0 == h1 + w1:
        return True
    return False

def prod_matrix(left, right):
    n = len(left)
    new_matrix = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                new_matrix[i][j] += (left[i][k] * right[k][j]) % MOD
                new_matrix[i][j] %= MOD
    return new_matrix

def prod_vector(matrix, vector):
    n = len(vector)
    new_vector = [0] * n
    for i in range(n):
        for j in range(n):
            new_vector[i] += (matrix[i][j] * vector[j]) % MOD
            new_vector[i] %= MOD
    return new_vector

def main():
    H, W, sx, sy, gx, gy, K = map(int, input().split())
    sx -= 1
    sy -= 1
    gx -= 1
    gy -= 1

    cell_count = H * W
    # 移動できる範囲を計算する
    next_move = [[] for _ in range(cell_count * (2 ** cell_count))]
    for state_index in range(cell_count * (2 ** cell_count)):
        current_pos = state_index % cell_count
        current_h = current_pos // W
        current_w = current_pos % W

        visited_bit = state_index // cell_count
        if visited_bit > 0 and visited_bit & ( 1 << current_pos) == 0:
            continue

        for new_h in range(H):
            for new_w in range(W):
                if new_h == current_h and new_w == current_w:
                    continue

                if same_line(new_h, new_w, current_h, current_w):
                    new_pos = new_h * W + new_w
                    if visited_bit & (1 << new_pos) == 0:
                        new_visited_state = visited_bit | ( 1 << new_pos)
                        new_state_index = new_visited_state * cell_count + new_pos
                        next_move[state_index].append(new_state_index)


    # 初期位置s0 -> 全てのますを一度訪問するまで、最後の位置t0にいたるまでの移動方法の通りを計算
    matrix = [[0] * cell_count for _ in range(cell_count)] 
    def ddd(x):
        y = x // cell_count
        return y.bit_count()
    start_array = [i for i in range(cell_count * (2 ** cell_count))]
    start_array.sort(key=ddd)

    for start_pos_index in range(cell_count):
        dp = [0] * (cell_count * (2 ** cell_count))
        start_state = start_pos_index
        dp[start_state] = 1

        for state in start_array:
            for new_state in next_move[state]:
                dp[new_state] += dp[state]
                dp[new_state] %= MOD

        for goal_pos_index in range(cell_count):
            goal_state = goal_pos_index + cell_count * (2 ** cell_count - 1)
            matrix[goal_pos_index][start_pos_index] = dp[goal_state]

    # 行列累乗で計算
    cycle_k_count = K // cell_count
    vector = [0] * cell_count
    vector[sx * W + sy] = 1
    while cycle_k_count > 0:
        if cycle_k_count % 2 == 1:
            vector = prod_vector(matrix, vector)

        matrix = prod_matrix(matrix, matrix)
        cycle_k_count //= 2

    # 最終的な位置計算 
    rest_k_count = K % cell_count
    dp = [0] * (cell_count * (2 ** cell_count))
    for i in range(cell_count):
        start_state = i
        dp[start_state] = vector[i]

    for state in start_array:
        for new_state in next_move[state]:
            dp[new_state] += dp[state]
            dp[new_state] %= MOD

    answer = 0
    goal_pos_index = (gx * W + gy)
    for bit in range(2 ** cell_count):
        if bit.bit_count() == rest_k_count:
            if bit == 0 or (bit & (1 << goal_pos_index) > 0):
                target_state = bit * cell_count
                target_state += goal_pos_index
                answer += dp[target_state]
                answer %= MOD
    print(answer)

    




    

                
                        

        







if __name__ == "__main__":
    main()