結果

問題 No.3600 Moving Queen Many Times
コンテスト
ユーザー hiryuN
提出日時 2026-07-24 22:16:13
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 3,670 ms / 7,000 ms
+ 321µs
コード長 1,555 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 236 ms
コンパイル使用メモリ 95,980 KB
実行使用メモリ 217,088 KB
最終ジャッジ日時 2026-07-24 22:19:46
合計ジャッジ時間 35,203 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 75
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

h,w,a,b,x,y,kk=map(int,input().split())
a-=1
b-=1
x-=1
y-=1
s=a*w+b
g=x*w+y
n=h*w
def matmat(A,B):
    Ans=[]
    for i in range(n):
        Ans.append([0]*n)
    for i in range(n):
        for j in range(n):
            for k in range(n):
                Ans[i][j]+=A[i][k]*B[k][j]
            Ans[i][j]%=M
    return Ans
                
V=[]
for i in range(n):
    V.append([0]*n)

for i in range(n):
    for j in range(n):
        a,b,c,d=i//w,i%w,j//w,j%w
        if (a==c or b==d or abs(a-c)==abs(b-d)) and i!=j:
            V[i][j]=1
M=998244353
Ans=[]
for i in range(n):
    DP=[]
    for j in range(n):
        DP.append([0]*(2**n))
    DP[i][0]=1
    for bb in range(2**n):
        for j in range(n):
            for k in range(n):
                if V[j][k] and (bb ^ 2**k) > bb:
                    DP[k][bb+2**k]+=DP[j][bb]
                    DP[k][bb+2**k]%=M
    Ans.append(DP)

loop=[]
for i in range(n):
    loop.append([0]*n)
for i in range(n):
    for j in range(n):
        loop[i][j]=Ans[i][j][-1]

I=[]
for i in range(n):
    II=[0]*n
    II[i]=1
    I.append(II)

EX=[loop]
for i in range(60):
    EX.append(matmat(EX[-1],EX[-1]))

ll=kk//n
div=kk%n
#print(ll)
for i in range(60):
    if ll^(2**i)<ll:
        I=matmat(I,EX[i])
ans=0
Q=I
"""
for I in Q:
    print(I)
"""

for i in range(n):
    for j in range(2**n):
        num=j
        I=0
        for k in range(n):
            I+=num%2
            num//=2
        if I==div:
            ans+=Q[s][i]*Ans[i][g][j]
            ans%=M
print(ans)
0