結果

問題 No.1011 Infinite Stairs
コンテスト
ユーザー toyuzuko
提出日時 2020-03-30 23:39:00
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 627 bytes
コンパイル時間 312 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 68,224 KB
最終ジャッジ日時 2024-06-23 07:02:55
合計ジャッジ時間 4,355 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

N, D, K = map(int,input().split())

def power(base, exp, op=lambda x, y: x * y, ie=1):
    res = ie
    while exp:
        if exp & 1:
            res = op(res, base)
        base = op(base, base)
        exp >>= 1
    return res
    
def mul(f, g):
    h = [0 for _ in range(K + 1)]
    for i in range(K + 1):
        for j in range(K + 1):
            if i + j <= K:
                h[i + j] += f[i] * g[j]
                h[i + j] %= MOD
    return h

ie = [0 for _ in range(K + 1)]
ie[0] = 1

base = [0 for _ in range(K + 1)]
for i in range(1, D + 1):
    base[i] = 1
    
print(power(base, N, mul, ie)[K])
0