#F. Distance Sequence

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l
    Type: RemoteJudge 2000ms 256MiB

Distance Sequence

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面翻译

求有多少长度为 nn 的数列 AA，满足以下条件：

  • 1≤Ai≤M 1\leq A_i \leq M (1≤i≤N) (1 \le i \le N)
  • ∣Ai−Ai+1∣≥K |A_i - A_{i+1}| \geq K (1≤i≤N−1) (1 \le i\le N-1)

2≤n≤1000 2 \leq n \leq 1000 ，1≤m≤5000 1 \leq m \leq 5000 ，0≤k≤m−1 0 \leq k \leq m - 1

题目描述

長さ N N の整数からなる数列 A=(A1,…,AN) A=(A_1,\ldots,A_N) であって、以下の条件を全て満たすものは何通りありますか？

  • 1≤ Ai ≤ M 1\le\ A_i\ \le\ M (1 ≤ i ≤ N) (1\ \le\ i\ \le\ N)
  • ∣Ai − Ai+1∣ ≥ K |A_i\ -\ A_{i+1}|\ \geq\ K (1 ≤ i ≤ N − 1) (1\ \le\ i\ \le\ N\ -\ 1)

ただし、答えは非常に大きくなることがあるので、答えを 998244353 998244353 で割った余りを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

N N M M K K

输出格式

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

样例 #1

样例输入 #1

2 3 1

样例输出 #1

6

样例 #2

样例输入 #2

3 3 2

样例输出 #2

2

样例 #3

样例输入 #3

100 1000 500

样例输出 #3

657064711

提示

制約

  • 2 ≤ N ≤ 1000 2\ \leq\ N\ \leq\ 1000
  • 1 ≤ M ≤ 5000 1\ \leq\ M\ \leq\ 5000
  • 0 ≤ K ≤ M−1 0\ \leq\ K\ \leq\ M-1
  • 入力は全て整数

Sample Explanation 1

条件を満たす数列は以下の 6 6 つです。 - (1,2) (1,2) - (1,3) (1,3) - (2,1) (2,1) - (2,3) (2,3) - (3,1) (3,1) - (3,2) (3,2)

Sample Explanation 2

条件を満たす数列は以下の 2 2 つです。 - (1,3,1) (1,3,1) - (3,1,3) (3,1,3)

Sample Explanation 3

答えを 998244353 998244353 で割った余りを出力してください。

北辰OI提高组第2周序列问题课后练习题👍

Not Attended
Status
Done
Rule
IOI
Problem
44
Start at
2024-1-7 16:00
End at
2024-2-18 8:00
Duration
1000 hour(s)
Host
Partic.
15
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. text

  4. 鲁公网安备 37079402001599号

  • 鲁ICP备2022025036号-1
  • Worker 0, 33ms
  • Powered by Hydro v4.9.27 Community