問題一覧 > 通常問題

No.1929 Exponential Sequence

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

問題文

長さ nn の整数列 {ai}\{a_i \} 及び正整数 SS が与えられます。

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

  • すべての ii について 1≤ki1 \le k_i
  • ∑i=1naiki≤S\displaystyle\sum_{i=1}^{n} {a_i}^{k_i} \le S

制約

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

入力

n Sn\ S
a1 a2 …ana_1\ a_2\ \dots a_n

出力

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

サンプル

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

{k1,k2,k3}={1,1,1},{1,1,2},{1,2,1},{2,1,1},{2,2,1},{3,1,1},{3,2,1}\{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

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

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

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

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