結果

問題 No.1403 調和の魔法陣
ユーザー 37zigen37zigen
提出日時 2020-07-21 17:23:36
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
RE  
実行時間 -
コード長 1,905 bytes
コンパイル時間 202 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2024-09-14 20:42:07
合計ジャッジ時間 1,678 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD=998244353
N=9

def solve(W,H,X):
    ans=0
    for min_e in range(N+1):
        for max_e in range(min_e,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=pow(d,H//2-1,MOD)-2*pow(d-1,H//2-1,MOD)+pow(max(0,d-2),H//2-1,MOD)
                pat_e%=MOD
            for min_o in range(N+1):
                for max_o in range(min_o, N+1):
                    pat_o=pow(max_o-min_o+1,H//2,MOD)-2*pow(max_o-min_o,H//2,MOD)+pow(max(0,max_o-min_o-1),H//2,MOD)
                    pat_o%=MOD
                    for a00 in range(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=pow(upper_o-lower_o+1,W//2,MOD)*pow(upper_e-lower_e+1,W//2-1,MOD)%MOD*pat_e%MOD*pat_o%MOD
                        add%=MOD
                        ans=(ans+add)%MOD
    print(ans)

W,H,X=map(int,input().split())
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:
    solve((W+1)//3*2,(H+1)//3*2,X)
else:
    raise Exception
0