結果

問題 No.269 見栄っ張りの募金活動
ユーザー susami-jpg
提出日時 2022-03-16 12:30:17
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,250 ms / 5,000 ms
コード長 2,246 bytes
コンパイル時間 270 ms
コンパイル使用メモリ 82,392 KB
実行使用メモリ 369,980 KB
最終ジャッジ日時 2024-09-24 09:01:04
合計ジャッジ時間 8,918 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

from sys import exit, stdin, setrecursionlimit
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, deque, Counter
from heapq import heappop, heappush, heapify
#from itertools import permutations, combinations, accumulate
#from math import sqrt, factorial
#math.log(x, y)はyを底としたxの対数を返す。
#数学ではlogとかlnで表される自然対数（ネイピア数eを底とする対数）は、math.log(x)で計算できる。
#二進対数（2を底とする対数）は、math.log2(x)で計算できる。math.log(x, 2)よりも正確な値となる。
#常用対数（10を底とする対数）は、math.log10(x)で計算できる。math.log(x, 10)よりも正確な値となる。
#from decimal import Decimal, ROUND_HALF_UP
#decimalには文字列で渡す PyPyは遅いのでPython3で提出する
#d1 = Decimal('1.1') d2 = Decimal('2.3') -> d1 + d2などの演算で浮動小数点数での誤差がなくなる(割り算もok)
#四捨五入: dをDecimalオブジェクトとして、d.quantize(Decimal('1'), rounding=ROUND_HALF_UP)) (1にすると整数を返し、0.1にすると小数第一位で四捨五入)
INF = 10**18
MOD = 10**9+7
MOD2 = 998244353
eps = 0.0000000001
setrecursionlimit(10**7)
#pypyでの再帰TLE対策(自分の環境では使えないので提出時のみコメントアウトするように注意)
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')
#list複数行読み込み高速化 改行、空白区切り注意
#[list(map(int, stdin.readline().split())) for _ in range(M)]
#複数行読み込み　行ごとに文字列として読み込む ex) ['9 2 6 5 3', '改行', '5 8 9 7 9', '改行'] 改行区切りなのと空白区切りをsplitする必要があるので注意
#query = stdin.readlines()

N, S, K = map(int, input().split())
#dfs(i, T):= i番目の支払金額まで決まっていて、残額がT円の時の支払う場合の数
rec = dict()
def dfs(i, T):
    if (i, T) in rec:return rec[(i, T)]
    if T < 0:return 0
    if i == 1:
        if T%N == 0:return 1
        else:return 0
    res = dfs(i-1, T-(N-i+1)*K) + dfs(i, T-(N-i+1))
    res %= MOD
    rec[(i, T)] = res
    return res

print(dfs(N, S))
0