No.2561 みんな大好きmod 998
タグ : / 解いたユーザー数 210
作問者 :
AngrySadEight
Kyo_s_s
kusirakusira
Magentor
loop0919
rotti_coder
ragna
マベマス（mavemas_413）
けんぴん
aki
問題文
$N$ 個の整数 $A_1, A_2,\ldots, A_N$ が与えられます。
ここで, $1 \leq x_1 < x_2 < \ldots < x_K \leq N$ となるような $K$ 個の整数 $(x_1, x_2, \ldots, x_K)$ を選択し, $A_{x_1}, A_{x_2}, \ldots, A_{x_K}$ の総和を $S$ とします。
また, 以下のように $S_{998}$, $S_{998244353}$ を定義します。
- $S_{998} = S\bmod 998$
- $S_{998244353} = S\bmod 998244353$
ただし, 答えは少し大きくなる可能性があるので, $998$ で割った余りを出力してください。
modとは？
$a\bmod b$ とは, $a$ を $b$ で割った余りを指します。例えば, $7 \bmod 3 = 1$ です。
制約
- $1 \leq N \leq 28$
- $1 \leq K \leq \min( 8, N )$
- $0 \leq A_i \leq 998244352$
- 入力はすべて整数である
入力
$N\,K$ $A_1 \,A_2 \,\ldots \,A_N$
出力
答えを $998$ で割った余りを出力せよ。
サンプル
サンプル1
入力
4 2 300 400 500 600
出力
4
$(x_1, x_2)$ として考えられる組み合わせは, $(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)$ の $6$ 通りです。
たとえば, $(1, 2)$を選択したとき, $S=A_1 + A_2 = 300 + 400 = 700, S_{998244353}=700, S_{998}=700$ なので $S_{998244353} \leq S_{998}$ を満たします。
また, $(3, 4)$ を選択したとき, $S=A_3 + A_4 = 500 + 600 = 1100, S_{998244353}=1100, S_{998}=102$ なので $S_{998244353} \leq S_{998}$ を満たしません。
同様に考えると, 条件を満たすのは $(1, 2), (1, 3), (1, 4), (2, 3)$ の $4$ 通りであることがわかります。
サンプル2
入力
20 8 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
出力
222
求める答えは $125970$ 通りです。$998$ で割った余りを出力することに注意してください。
サンプル3
入力
8 8 812087642 562447828 487989038 879550309 409027146 501712355 131601217 18035145
出力
0
$S$ は32bit整数型に収まらない場合があることに注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。