結果

問題 No.498 ワープクリスタル (給料日編)
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:44:29
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 142 ms / 2,000 ms
コード長 1,352 bytes
コンパイル時間 259 ms
コンパイル使用メモリ 82,252 KB
実行使用メモリ 76,708 KB
最終ジャッジ日時 2025-03-20 20:44:48
合計ジャッジ時間 3,464 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

Gx, Gy, K = map(int, input().split())
crystals = []
for _ in range(K):
    x, y, n = map(int, input().split())
    crystals.append((x, y, n))

max_sum_m = sum(n for _, _, n in crystals)
# Precompute factorial and inverse factorial mod MOD up to max_sum_m
max_fact = max_sum_m
fact = [1] * (max_fact + 1)
for i in range(1, max_fact + 1):
    fact[i] = fact[i-1] * i % MOD

inv_fact = [1] * (max_fact + 1)
inv_fact[max_fact] = pow(fact[max_fact], MOD-2, MOD)
for i in range(max_fact - 1, -1, -1):
    inv_fact[i] = inv_fact[i+1] * (i+1) % MOD

ans = 0

def backtrack(k, curr_x, curr_y, used):
    global ans
    if k == K:
        if curr_x == Gx and curr_y == Gy:
            sum_m = sum(used)
            if sum_m == 0:
                # Check if (0,0) is the target
                if Gx == 0 and Gy == 0:
                    ans = (ans + 1) % MOD
                return
            numerator = fact[sum_m]
            denominator = 1
            for m in used:
                denominator = denominator * inv_fact[m] % MOD
            res = numerator * denominator % MOD
            ans = (ans + res) % MOD
        return
    x, y, n = crystals[k]
    for m in range(0, n + 1):
        next_x = curr_x + x * m
        next_y = curr_y + y * m
        backtrack(k+1, next_x, next_y, used + [m])

backtrack(0, 0, 0, [])
print(ans % MOD)
0