問題一覧 > 通常問題

No.2561 Everyone's Favorite mod 998

レベル : / AI推定難易度 : 600 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 229
作問者 : deuteridayo / テスター : 👑 AngrySadEight Kyo_s_s kusirakusira Magentor 👑 loop0919 rotti_coder ragna マベマス（mavemas_413） けんぴん aki
お気に入りにしたユーザー ProblemId : 10160 / 自分の提出
問題文最終更新日: 2023-11-30 18:44:32
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
第2回緑以下コンテスト (順位表) の他の問題:

Problem Statement

You are given $N$ integers $A_1, A_2,\ldots, A_N$.
Choose $K$ integers $(x_1, x_2, \ldots, x_K)$ such that $1 \leq x_1 < x_2 < \ldots < x_K \leq N$, and let $S$ be the sum of $A_{x_1}, A_{x_2}, \ldots, A_{x_K}$.
Also, define $S_{998}$ and $S_{998244353}$ as follows.

  • $S_{998} = S\bmod 998$
  • $S_{998244353} = S\bmod 998244353$
Find the number of ways to choose $(x_1, x_2, \ldots, x_K)$ such that $S_{998244353} \leq S_{998}$.
Since the answer may be somewhat large, print it modulo $998$.

What is mod? $a\bmod b$ denotes the remainder when $a$ is divided by $b$.
For example, $7 \bmod 3 = 1$.

Constraints

  • $1 \leq N \leq 28$
  • $1 \leq K \leq \min( 8, N )$
  • $0 \leq A_i \leq 998244352$
  • All inputs are integers.

Input

$N\,K$
$A_1 \,A_2 \,\ldots \,A_N$

Output

Print the answer modulo $998$.

Sample

Sample 1
Input
4 2
300 400 500 600
Output
4

There are $6$ possible combinations for $(x_1, x_2)$: $(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)$.
For example, if $(1, 2)$ is chosen, then $S=A_1 + A_2 = 300 + 400 = 700, S_{998244353}=700, S_{998}=700$, so $S_{998244353} \leq S_{998}$ is satisfied.
If $(3, 4)$ is chosen, then $S=A_3 + A_4 = 500 + 600 = 1100, S_{998244353}=1100, S_{998}=102$, so $S_{998244353} \leq S_{998}$ is not satisfied.
Considering the others in the same way, we can see that the condition is satisfied by $4$ ways: $(1, 2), (1, 3), (1, 4), (2, 3)$.

Sample 2
Input
20 8
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
Output
222

The number of ways is $125970$. Note that you must print it modulo $998$.

Sample 3
Input
8 8
812087642 562447828 487989038 879550309 409027146 501712355 131601217 18035145
Output
0

Note that $S$ may not fit in a 32-bit integer type.

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