結果

問題 No.1403 調和の魔法陣
ユーザー qwewe
提出日時 2025-05-14 12:50:01
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,700 bytes
コンパイル時間 330 ms
コンパイル使用メモリ 82,632 KB
実行使用メモリ 71,076 KB
最終ジャッジ日時 2025-05-14 12:51:18
合計ジャッジ時間 2,832 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod = 998244353

# Precompute ways[s] = number of pairs (a, b) with a + b = s and 0 <= a, b <= 9
ways = [0] * 19
for s in range(19):
    if s <= 9:
        ways[s] = s + 1
    else:
        ways[s] = 19 - s

def comb(n, k):
    if n < k or k < 0:
        return 0
    res = 1
    for i in range(k):
        res = res * (n - i) // (i + 1)
    return res % mod

def compute_case(W, H, X):
    if X < 0 or X > 81:
        return 0
    if H == 1 and W == 1:
        return 1 if 0 <= X <= 9 else 0
    elif H == 1 and W == 2:
        return ways[X] % mod if X <= 18 else 0
    elif H == 2 and W == 2:
        total = comb(X + 3, 3)
        total -= 4 * comb(X - 10 + 3, 3)
        total += 6 * comb(X - 20 + 3, 3)
        total -= 4 * comb(X - 30 + 3, 3)
        total += comb(X - 40 + 3, 3)
        total %= mod
        return max(total, 0) % mod
    elif H == 2 and W % 2 == 1:
        m = (W - 1) // 2
        res = 0
        for s in range(X + 1):
            t = X - s
            if s > 18 or t < 0 or t > 18:
                continue
            term = (ways[s] * ways[t]) % mod
            res = (res + pow(term, m, mod)) % mod
        return res % mod
    elif H == 2 and W % 2 == 0:
        m = W // 2
        res = 0
        for s in range(X + 1):
            t = X - s
            if s > 18 or t < 0 or t > 18:
                continue
            term = (ways[s] * ways[t]) % mod
            res = (res + pow(term, m, mod)) % mod
        return res % mod
    else:
        return 0

import sys
input = sys.stdin.read().split()
T = int(input[0])
idx = 1
for _ in range(T):
    W = int(input[idx])
    H = int(input[idx+1])
    X = int(input[idx+2])
    idx +=3
    print(compute_case(W, H, X))
0