問題一覧 > 通常問題

No.1782 ManyCoins

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 32
作問者 : ei1333333ei1333333 / テスター : LuzhiledLuzhiled
12 ProblemId : 7367 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-12-08 17:45:00

問題文

硬貨 $1$ から硬貨 $N$ までの $N$ 種類の硬貨が, それぞれ $10^{100000}$ 枚あります。硬貨 $i\ (1 \leq i \leq N)$ の $1$ 枚あたりの価値は $W_i$ です。

$1$ 以上 $L$ 以下の価値のうち, 硬貨を $1$ 枚以上選ぶことで作れる価値が何種類あるか求めてください。 同じ種類の硬貨を複数枚選んでも構いません。

正式には, 以下の条件をすべて満たす整数 $k$ の個数を求めてください。

  • $1 \leq k \leq L$
  • $\displaystyle \sum_{i=1}^{N} c_i W_i = k$ を満たす長さ $N$ の非負整数列 $c$ が存在する

入力

$N$ $L$
$W_1$ $W_2$ $\cdots$ $W_N$
  • $1 \leq N \leq 20$
  • $1 \leq L \leq 10^{12}$
  • $1 \leq W_i \leq 10^6$
  • $i \neq j$ ならば $W_i \ne W_j$
  • 入力はすべて整数

出力

$1$ 行に答えを出力してください。

サンプル

サンプル1
入力
2 10
5 2
出力
8

価値の和が $2, 4, 5, 6, 7, 8, 9, 10$ となる選び方が存在します。

サンプル2
入力
5 30014
10001 10002 10003 10004 10005
出力
26
サンプル3
入力
3 1000000000000
1 2 3
出力
1000000000000

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。