/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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