問題一覧 > 通常問題

No.1929 Exponential Sequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 76
作問者 : 👑 nullnull / テスター : とりゐとりゐ
7 ProblemId : 7179 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-25 18:01:14

問題文

長さ $n$ の整数列 $\{a_i \}$ 及び正整数 $S$ が与えられます。

次の条件を満たす長さ $n$ の整数列 $\{k_i \}$ を数え上げてください。

  • すべての $i$ について $1 \le k_i$
  • $\displaystyle\sum_{i=1}^{n} {a_i}^{k_i} \le S$

制約

  • $1 \le n \le 8$
  • $2 \le S, a_i \le 10^9$
  • 入力はすべて整数。

入力

$n\ S$
$a_1\ a_2\ \dots a_n$

出力

答えを出力してください。最後に改行してください。

サンプル

サンプル1
入力
3 21
2 3 4
出力
7

$\{k_1, k_2, k_3\} = \{ 1, 1, 1 \}, \{ 1, 1, 2\}, \{ 1, 2, 1 \}, \{2, 1, 1\}, \{2, 2, 1 \}, \{3, 1, 1 \}, \{3, 2, 1 \}$ のみが条件を満たします。

サンプル2
入力
4 124
13 133 1333 13333
出力
0

答えが $0$ の場合もあります。

サンプル3
入力
5 1000000000
65536 2 37 382759279 15
出力
1009

サンプル4
入力
8 1000000000
2 2 2 2 2 2 2 2
出力
481891820460

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