結果

問題 No.1403 調和の魔法陣
コンテスト
ユーザー 37zigen
提出日時 2020-08-13 19:58:36
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 2,239 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 22,144 KB
最終ジャッジ日時 2024-09-14 20:44:14
合計ジャッジ時間 5,035 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

# online O(N^5）解

MOD=998244353
N=9

pows=[]
for n in range(11):
    a=[1]
    for i in range(601):
        a.append(a[-1]*n%MOD)
    pows.append(a)

def solvesub(W,H,X):
    ans=0
    for min_e in range(min(X+1,N+1)):
        for max_e in range(min_e,min(X+1,N+1)):
            if H==2 and not (min_e==0 and max_e==0):
                continue
            if H==2:
                pat_e=1
            else:
                d=max_e-min_e+1
                pat_e=pows[d][H//2-1]-2*pows[d-1][H//2-1]+pows[max(0,d-2)][H//2-1]
                pat_e%=MOD
            for min_o in range(min(X+1,N+1)):
                for max_o in range(min_o, N+1):
                    pat_o=pows[max_o-min_o+1][H//2]-2*pows[max_o-min_o][H//2]+pows[max(0,max_o-min_o-1)][H//2]
                    pat_o%=MOD
                    for a00 in range(min(X+1,N+1)):
                        upper_o=min(X-a00-max_o,N)
                        lower_o=max(X-a00-N-min_o,0)
                        upper_e=min(a00+min_o,N)
                        lower_e=max(-N+a00+max_o,0)
                        if H>=3:
                            upper_o=min(upper_o,N-a00+min_e)
                            lower_o=max(lower_o,-a00+max_e)
                            upper_e=min(upper_e,N+a00-max_e)
                            lower_e=max(lower_e,a00-min_e)
                        if upper_o-lower_o<0 or (W>2 and upper_e-lower_e<0):
                            continue
                        add=pows[upper_o-lower_o+1][W//2]*pows[upper_e-lower_e+1][W//2-1]%MOD*pat_e%MOD*pat_o%MOD
                        ans=ans+add
                        ans=(ans+add)%MOD
    print(ans)

def solve(W,H,X):
    if W%3>H%3:
        W,H=H,W
    if (W%3==0 and H%3==0) or (W%3==0 and H%3==1) or (W%3==1 and H%3==1):
        print(int(X<=N))
    elif W%3==0 and H%3==2:
        d=min(N,X)-max(0,X-N)+1
        d=max(0,d)
        print(pow(d,W//3,MOD))
    elif W%3==1 and H%3==2:
        d=min(N,X)-max(0,X-N)+1
        d=max(0,d)
        print(pow(d,(W+2)//3,MOD))
    elif W%3==2 and H%3==2:
        solvesub((W+1)//3*2,(H+1)//3*2,X)
    else:
        raise Exception

def run():
    T=int(input())
    for t in range(T):
        W,H,X=map(int,input().split())
        solve(W,H,X)
run()
0