No.3391 Line up Dominoes
レベル :
/ AI推定難易度 : 1100
/ 実行時間制限 : 1ケース 3.000秒 / メモリ制限
: 128 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 66
作問者 :
yu23578
/ テスター :
GaLLium
yt142857
aa36
Germanium32
タグ : / 解いたユーザー数 66
作問者 :
yu23578
/ テスター :
GaLLium
yt142857
aa36
Germanium32
問題文最終更新日: 2025-11-28 22:03:27
English (AI translation)
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
yukicoder contest 490
(順位表)
の他の問題:
Problem Statement
yu23578 has $N$ types of dominoes numbered from $1$ to $N$, with $10^{100}$ dominoes of each type. The size of domino $i$ is $A_i$.
yu23578 has decided to choose $M$ dominoes from these and line them up in a horizontal row. Find the total number of ways to place the dominoes satisfying the following condition, modulo $\mathrm{mod} 998244353$.
- The difference in size between adjacent dominoes is at most $K$.
Constraints
- $1 \le N,M \le 10^4$
- $0 \le K \le 10^9$
- $1 \le A_i \le 10^9$
- All input values are integers.
Input
$N\ M\ K$ $A_1\ A_2\ A_3\ \cdots\ A_N$
Output
Output the total number of ways to place the dominoes satisfying the condition, modulo $\mathrm{mod} 998244353$.
Print a newline at the end.
Sample
Sample 1
Input
3 2 2 3 1 4
Output
7
The arrangements satisfying the condition are the following
(domino $1,$ domino $1$ )
(domino $1,$ domino $2$ )
(domino $1,$ domino $3$ )
(domino $2,$ domino $1$ )
(domino $2,$ domino $2$ )
(domino $3,$ domino $2$ )
(domino $3,$ domino $3$ )
for a total of $7$ ways, so output $7$.
Sample 2
Input
1 1 1000000000 1000000000
Output
1
Sample 3
Input
2 357 82 35 78
Output
782487810
Answer modulo $\mathrm{mod} 998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。