結果

問題 No.269 見栄っ張りの募金活動
ユーザー susami-jpgsusami-jpg
提出日時 2022-03-16 12:30:17
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,637 ms / 5,000 ms
コード長 2,246 bytes
コンパイル時間 425 ms
コンパイル使用メモリ 81,636 KB
実行使用メモリ 369,300 KB
最終ジャッジ日時 2023-10-24 17:16:04
合計ジャッジ時間 10,380 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
55,496 KB
testcase_01 AC 44 ms
55,496 KB
testcase_02 AC 63 ms
76,652 KB
testcase_03 AC 150 ms
94,748 KB
testcase_04 AC 1,001 ms
298,264 KB
testcase_05 AC 57 ms
65,932 KB
testcase_06 AC 44 ms
55,564 KB
testcase_07 AC 2,637 ms
369,300 KB
testcase_08 AC 71 ms
55,452 KB
testcase_09 AC 525 ms
196,696 KB
testcase_10 AC 52 ms
65,848 KB
testcase_11 AC 283 ms
133,424 KB
testcase_12 AC 312 ms
142,784 KB
testcase_13 AC 306 ms
134,468 KB
testcase_14 AC 109 ms
97,400 KB
testcase_15 AC 279 ms
128,092 KB
testcase_16 AC 401 ms
157,380 KB
testcase_17 AC 89 ms
82,344 KB
testcase_18 AC 1,251 ms
272,552 KB
testcase_19 AC 337 ms
146,276 KB
testcase_20 AC 94 ms
84,260 KB
testcase_21 AC 149 ms
101,176 KB
testcase_22 AC 171 ms
96,684 KB
testcase_23 AC 72 ms
79,480 KB
testcase_24 AC 127 ms
94,960 KB
権限があれば一括ダウンロードができます

ソースコード

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