問題一覧 > 通常問題

No.2561 みんな大好きmod 998

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 218
作問者 : deuteridayo / テスター : 👑 AngrySadEight Kyo_s_s kusirakusira Magentor 👑 loop0919 rotti_coder ragna マベマス（mavemas_413） けんぴん aki
4 ProblemId : 10160 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-11-30 18:44:32

問題文

NN 個の整数 A1,A2,…,ANA_1, A_2,\ldots, A_N が与えられます。
ここで, 1≤x1<x2<…<xK≤N1 \leq x_1 < x_2 < \ldots < x_K \leq N となるような KK 個の整数 (x1,x2,…,xK)(x_1, x_2, \ldots, x_K) を選択し, Ax1,Ax2,…,AxKA_{x_1}, A_{x_2}, \ldots, A_{x_K} の総和を SS とします。
また, 以下のように S998S_{998}, S998244353S_{998244353} を定義します。

  • S998=S mod 998S_{998} = S\bmod 998
  • S998244353=S mod 998244353S_{998244353} = S\bmod 998244353
このとき, S998244353≤S998S_{998244353} \leq S_{998} となるような (x1,x2,…,xK)(x_1, x_2, \ldots, x_K) の選び方は何通りあるかを求めてください。
ただし, 答えは少し大きくなる可能性があるので, 998998 で割った余りを出力してください。

modとは？ a mod ba\bmod b とは, aa を bb で割った余りを指します。
例えば, 7 mod 3=17 \bmod 3 = 1 です。

制約

  • 1≤N≤281 \leq N \leq 28
  • 1≤K≤min⁡(8,N)1 \leq K \leq \min( 8, N )
  • 0≤Ai≤9982443520 \leq A_i \leq 998244352
  • 入力はすべて整数である

入力

N KN\,K
A1 A2 … ANA_1 \,A_2 \,\ldots \,A_N

出力

答えを 998998 で割った余りを出力せよ。

サンプル

サンプル1
入力
4 2
300 400 500 600
出力
4

(x1,x2)(x_1, x_2) として考えられる組み合わせは, (1,2),(1,3),(1,4),(2,3),(2,4),(3,4)(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4) の 66 通りです。
たとえば, (1,2)(1, 2)を選択したとき, S=A1+A2=300+400=700,S998244353=700,S998=700S=A_1 + A_2 = 300 + 400 = 700, S_{998244353}=700, S_{998}=700 なので S998244353≤S998S_{998244353} \leq S_{998} を満たします。
また, (3,4)(3, 4) を選択したとき, S=A3+A4=500+600=1100,S998244353=1100,S998=102S=A_3 + A_4 = 500 + 600 = 1100, S_{998244353}=1100, S_{998}=102 なので S998244353≤S998S_{998244353} \leq S_{998} を満たしません。
同様に考えると, 条件を満たすのは (1,2),(1,3),(1,4),(2,3)(1, 2), (1, 3), (1, 4), (2, 3) の 44 通りであることがわかります。

サンプル2
入力
20 8
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
出力
222

求める答えは 125970125970 通りです。998998 で割った余りを出力することに注意してください。

サンプル3
入力
8 8
812087642 562447828 487989038 879550309 409027146 501712355 131601217 18035145
出力
0

SS は32bit整数型に収まらない場合があることに注意してください。

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