結果

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

ソースコード

diff #
raw source code 

mod = 998244353

h,w,sy,sx,gy,gx,KK = list(map(int,input().split()))
sy,sx,gy,gx = sy-1,sx-1,gy-1,gx-1
hw = h*w
s = [[[0 for i in range(2**hw)] for u in range(hw)]for k in range(hw)]

for y in range(h):
    for x in range(w):
        xy = y*w+x
        for Y in range(h):
            for X in range(w):
                XY = Y*w+X
                if xy == XY:
                    continue
                if y == Y or x == X or x+y == X+Y or x-y == X-Y:
                    s[xy][XY][1<<XY] = 1

for i in range(hw):
    for bit in range(2**hw):
        for y in range(h):
            for x in range(w):
                xy = y*w+x
                if bit&(1<<xy) == 0:
                    continue
                for Y in range(h):
                    for X in range(w):
                        XY = Y*w+X
                        if bit&(1<<XY):
                            continue
                        if y == Y or x == X or x+y == X+Y or x-y == X-Y:
                            s[i][XY][bit|(1<<XY)] += s[i][xy][bit]
                            s[i][XY][bit|(1<<XY)] %= mod

t = [[s[i][u][2**hw-1] for u in range(hw)] for i in range(hw)]
out = [0 for i in range(hw)]
out[sy*w+sx] = 1
K = KK//hw

while K:
    if K&1:
        a = [0 for i in range(hw)]
        for i in range(hw):
            for u in range(hw):
                a[u] += out[i]*t[i][u]
                a[u] %= mod
        out = a[:]
    
    b = [[0 for i in range(hw)] for u in range(hw)]
    
    for i in range(hw):
        for u in range(hw):
            for k in range(hw):
                b[i][k] += t[i][u]*t[u][k]
                b[i][k] %= mod
    
    t = b[:]
    K //= 2

K = KK%hw
ans = 0

if K:
    for bit in range(2**hw):
        c = 0
        for i in range(hw):
            if bit&(1<<i):
                c += 1
        if c != K:
            continue
        
        for i in range(hw):
            ans += out[i]*s[i][gy*w+gx][bit]
            ans %= mod

elif K == 0:
    ans += out[gy*w+gx]
    ans %= mod

print(ans)
0