結果

問題 No.137 貯金箱の焦り
ユーザー 👑 SPD_9X2
提出日時 2025-07-19 18:25:19
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 624 bytes
コンパイル時間 609 ms
コンパイル使用メモリ 82,964 KB
実行使用メモリ 77,624 KB
最終ジャッジ日時 2025-07-19 18:25:28
合計ジャッジ時間 9,027 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict

mod = 1234567891

N,M = map(int,input().split())
A = list(map(int,input().split()))

dp = defaultdict(int)
dp[0] = 1

for bit in range(60):

    nbit = 2**bit
    adds = [ a * nbit for a in A ]

    for add in adds:

        snapshot = list(dp.items())

        for s,v in snapshot:
            if s+add > M:
                continue
            dp[s+add] += v
            dp[s+add] %= mod
        
    ndp = defaultdict(int)
    mask = (2**(bit+1))-1
    for k in dp:
        if (k&mask) == (M&mask) and k <= M:
            ndp[k] = dp[k]
    dp = ndp

    # print (dp)

print (dp[M])
0