問題一覧 > 通常問題

No.1463 Hungry Kanten

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 123
作問者 : Kanten4205Kanten4205 / テスター : MtSakaMtSaka
3 ProblemId : 4882 / 出題時の順位表
問題文最終更新日: 2021-04-02 21:37:08

問題文

今、冷蔵庫には、$N$個の整数$A_i(1 \leq i \leq N)$が入っています。お腹が空いてしまったかんてん君は、大好物の整数を食べることにしました。
そのままでは食べることができないので、かんてん君は、$K$個以上の整数を選んで、次の操作のどちらかを1回のみ行い、できた整数を食べます。
・加熱調理 - 選んだ整数を全て混ぜて、加熱します。できる整数は、選んだ整数の総和です。
・加圧調理 - 選んだ整数を全て圧力器の中に入れ、加圧します。できる整数は、選んだ整数の総積です。
調理方法がこの2つしか存在しないとすると、かんてん君が食べることのできる整数は何種類あるでしょう?

入力

$N\ K$
$A_1\ A_2\ \cdots\ A_N$

すべてのテストケースは、次の制約を満たします。
・$2 \leq N \leq 18$
・$2 \leq K \leq N$
・$1 \leq A_i \leq 10^3(1 \leq i \leq N)$
・入力は全て整数

出力

かんてん君が食べることのできる整数の種類数を1行に出力してください。また、最後に改行してください。

サンプル

サンプル1
入力
4 2
1 2 3 5
出力
12

これらの整数を調理することで、かんてん君は $2,3,4,5,6,7,8,9,10,11,15,30$の12個の整数を食べることができます。

サンプル2
入力
2 2
2 2
出力
1

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