結果

問題 No.498 ワープクリスタル (給料日編)
コンテスト
ユーザー roaris
提出日時 2019-12-16 16:31:19
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,821 ms / 2,000 ms
コード長 754 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 214 ms
コンパイル使用メモリ 85,632 KB
実行使用メモリ 83,072 KB
最終ジャッジ日時 2026-03-24 03:45:46
合計ジャッジ時間 26,724 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import deque

def inv(x):
    return pow(x, MOD-2, MOD)
    
def dfs(d, q):
    if d==K:
        x, y = 0, 0
        res = fact[sum(q)]
        
        for (xi, yi, _), qi in zip(xyN, q):
            x += xi*qi
            y += yi*qi
            res *= inv(fact[qi])
            
        if x==Gx and y==Gy:
            return res
        else:
            return 0
            
    res = 0
    
    for i in range(xyN[d][2]+1):
        q.append(i)
        res += dfs(d+1, q)
        res %= MOD
        q.pop()
    
    return res

Gx, Gy, K = map(int, input().split())
xyN = [tuple(map(int, input().split())) for _ in range(K)]
MOD = 10**9+7
fact = [1]

for i in range(1, 100):
    fact.append(fact[-1]*i%MOD)

print(dfs(0, deque([])))
0