結果

問題 No.3600 Moving Queen Many Times
コンテスト
ユーザー kidodesu
提出日時 2026-07-24 23:44:30
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 2,567 ms / 7,000 ms
+ 554µs
コード長 2,324 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 258 ms
コンパイル使用メモリ 96,364 KB
実行使用メモリ 307,712 KB
最終ジャッジ日時 2026-07-24 23:45:00
合計ジャッジ時間 28,716 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 75
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

mod = 998244353
def main():
    h, w, sy, sx, gy, gx, k = list(map(int, input().split()))
    sy, sx, gy, gx = sy-1, sx-1, gy-1, gx-1
    N = h*w
    A = [[0]*N for _ in range(N)]
    for y0 in range(h):
        for x0 in range(w):
            dp = [[0]*N for _ in range(1<<N)]
            dp[0][y0*w+x0] = 1
            for bit in range(1<<N):
                for y1 in range(h):
                    for x1 in range(w):
                        if not dp[bit][y1*w+x1]: continue
                        for y2 in range(h):
                            for x2 in range(w):
                                if (y1, x1) == (y2, x2): continue
                                if bit >> (y2*w+x2) & 1: continue
                                nbit = bit | 1 << (y2*w+x2)
                                if y1 == y2 or x1 == x2 or y1+x1 == y2+x2 or y1-x1 == y2-x2:
                                    dp[nbit][y2*w+x2] = (dp[nbit][y2*w+x2] + dp[bit][y1*w+x1]) % mod
            for yx in range(N):
                A[y0*w+x0][yx] = dp[-1][yx]
    B = [0] * N
    B[sy*w+sx] = 1
    K = k // N
    for i in range(60):
        if K >> i & 1:
            nB = [0] * N
            for u in range(N):
                for v in range(N):
                    nB[v] = (nB[v] + B[u]*A[u][v]) % mod
            B = nB
        nA = [[0]*N for _ in range(N)]
        for m in range(N):
            for u in range(N):
                for v in range(N):
                    nA[u][v] = (nA[u][v] + A[u][m]*A[m][v]) % mod
        A = nA
    dp = [[0]*N for _ in range(1<<N)]
    for i in range(N):
        dp[0][i] = B[i]
    for bit in range(1<<N):
        for y1 in range(h):
            for x1 in range(w):
                if not dp[bit][y1*w+x1]: continue
                for y2 in range(h):
                    for x2 in range(w):
                        if bit >> (y2*w+x2) & 1: continue
                        if (y1, x1) == (y2, x2): continue
                        nbit = bit | 1 << (y2*w+x2)
                        if y1 == y2 or x1 == x2 or y1+x1 == y2+x2 or y1-x1 == y2-x2:
                            dp[nbit][y2*w+x2] = (dp[nbit][y2*w+x2] + dp[bit][y1*w+x1]) % mod
    ans = 0
    k = k % N
    for bit in range(1<<N):
        if bin(bit).count("1") == k:
            ans = (ans + dp[bit][gy*w+gx]) % mod
    return ans

print(main())
0