No.1929 Exponential Sequence
null
とりゐ問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。