Tenka1 Programmer Contest 2019

F - Banned X


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 1024MB

配点 : 800

問題文

0,1,2 のみからなる長さ N の数列であって、 どの連続する部分列に対してもそれに含まれる数の総和がちょうど X にはならないようなものの個数を 998244353 で割ったあまりを求めてください。

制約

  • 1 \leq N \leq 3000
  • 1 \leq X \leq 2N
  • N,X は整数である

入力

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

N X

出力

条件を満たす数列の個数を 998244353 で割ったあまりを出力せよ。


入力例 1

3 3

出力例 1

14

(0,0,0),(0,0,1),(0,0,2),(0,1,0),(0,1,1),(0,2,0),(0,2,2),(1,0,0),(1,0,1),(1,1,0),(2,0,0),(2,0,2),(2,2,0),(2,2,2)14 個の数列が条件を満たします。


入力例 2

8 6

出力例 2

1179

入力例 3

10 1

出力例 3

1024

入力例 4

9 13

出力例 4

18402

入力例 5

314 159

出力例 5

459765451

Score : 800 points

Problem Statement

Find the number, modulo 998244353, of sequences of length N consisting of 0, 1 and 2 such that none of their contiguous subsequences totals to X.

Constraints

  • 1 \leq N \leq 3000
  • 1 \leq X \leq 2N
  • N and X are integers.

Input

Input is given from Standard Input in the following format:

N X

Output

Print the number, modulo 998244353, of sequences that satisfy the condition.


Sample Input 1

3 3

Sample Output 1

14

14 sequences satisfy the condition: (0,0,0),(0,0,1),(0,0,2),(0,1,0),(0,1,1),(0,2,0),(0,2,2),(1,0,0),(1,0,1),(1,1,0),(2,0,0),(2,0,2),(2,2,0) and (2,2,2).


Sample Input 2

8 6

Sample Output 2

1179

Sample Input 3

10 1

Sample Output 3

1024

Sample Input 4

9 13

Sample Output 4

18402

Sample Input 5

314 159

Sample Output 5

459765451

Submit提出する