結果

問題 No.269 見栄っ張りの募金活動
ユーザー susami-jpgsusami-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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
55,524 KB
testcase_01 AC 42 ms
54,704 KB
testcase_02 AC 60 ms
76,912 KB
testcase_03 AC 146 ms
95,248 KB
testcase_04 AC 890 ms
298,676 KB
testcase_05 AC 49 ms
65,872 KB
testcase_06 AC 42 ms
55,188 KB
testcase_07 AC 2,250 ms
369,980 KB
testcase_08 AC 41 ms
55,300 KB
testcase_09 AC 466 ms
197,540 KB
testcase_10 AC 49 ms
65,352 KB
testcase_11 AC 247 ms
133,828 KB
testcase_12 AC 286 ms
143,444 KB
testcase_13 AC 284 ms
134,692 KB
testcase_14 AC 102 ms
97,508 KB
testcase_15 AC 260 ms
128,604 KB
testcase_16 AC 370 ms
157,664 KB
testcase_17 AC 86 ms
82,628 KB
testcase_18 AC 1,170 ms
273,248 KB
testcase_19 AC 305 ms
146,516 KB
testcase_20 AC 93 ms
84,776 KB
testcase_21 AC 139 ms
101,768 KB
testcase_22 AC 167 ms
97,336 KB
testcase_23 AC 69 ms
79,816 KB
testcase_24 AC 122 ms
95,176 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