Problem:
 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

Solution (Python):

"""
Writer: SPD_9X2
https://atcoder.jp/contests/tenka1-2019/tasks/tenka1_2019_f
Xが偶数か奇数かは重要な気がする
長さL(<=N)の1,2で構成された文字列の問題、に変換できる
O(L)で求められばおｋ
dpか？

X == 1なら、0,2のみで構成されてればおｋ
X == 2なら、1が2つ以上入っていたら不可能 0 & 1が1つまで
X == 3なら、2を入れる場合→1は入れられないが、2を好きなだけ入れていい
            入れない場合→1を2個まで入れられる
X == 4なら、

→やはり偶奇が重要か？

とどく場合は X-1　→ X+1の移動は強制
すなわち 座標1に行ってはいけない
初手は2に行くしかない
同様にX+2には行けない
X+3に行くしかない
3には行けないから4に行くしかない
つまり2以外不可？？ 

無限に移動を続ける場合は少なくともX=奇数 2のみ以外無理
偶数の場合はX以前に奇数回1をはさむ必要あり
a→a+1と移動すると、X+a-1から先は移動できなくなる

よって2Xは絶対超えられない
あとは数え上げにどうやって落とすか
Lは固定でいいと思うんだよな
O(L)で解ければ勝ち

dp ?
総和で場合分け or Lで場合分け
総和で場合分けする場合、当然Lは異なるのでまとめる必要がある
Lの長さの移動の寄与にはNCLを掛ける必要がある
移動するときにLは1増えるんだよな…
nC(l+1) = nCl * (n-l)/(l+1)
移動処理を一気に行えばlは統一できるからおｋ？

総和SはX以上の場合 X+1+2kしかありえない
S-X以前は2のみ進軍可能、以降は自由

対称性？
1と2の数を全探索？ ならばO(N**2)でいける
1がA個,2がB個の時、最初と最後に2をいくつか置く必要がある
→後は残りの位置から1を置く場所を選べばよい

→解けたっぽい？

場合分け頑張ろう

合計がX以下の場合→完全に自由
合計が2X以上の場合→Xが奇数の場合のみ all2が可能。それ以外は死
X以上2X以下の場合
→
    S-Xが奇数である必要あり
    まず2を(S-X+1)こ消費する（前後に置く分）
    あとは自由に順列を作ってどうぞ
    
"""

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv): 

    return fac[n] * inv[n-r] * inv[r] % mod


N,X = map(int,input().split())

mod = 998244353
fac,inv = modfac(N+10,mod)
ans = 0

for two in range(N+1):

    for one in range(N+1):

        if one + two > N:
            break
        
        dist = one + two*2
        zero = modnCr(N,one+two,mod,fac,inv)
        now = 0

        if dist < X:
            now = modnCr(one+two,one,mod,fac,inv) * zero
        elif dist == X:
            continue
        elif dist < 2*X:
            if (dist-X) % 2 == 0:
                continue
            dtwo = two - (dist-X+1)
            if dtwo >= 0:
                now = modnCr(one+dtwo,one,mod,fac,inv) * zero
        elif X % 2 == 1 and one == 0:
            now = zero

        
        
        ans += now
        ans %= mod

print (ans)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
N, X = map(int, input().split())
P = 998244353

A = [[0] * (2*i+1) for i in range(N+1)] 
A[0][0] = 1
B = [0] * (N + 1) 
for i in range(N):
    for j in range(i, 2*i+1):
        A[i+1][j+1] += A[i][j]
        A[i+1][j+2] += A[i][j]
        if A[i+1][j+1] >= P: A[i+1][j+1] -= P
        if A[i+1][j+2] >= P: A[i+1][j+2] -= P


for i in range(N+1):
    for j in range(i, min(2*i+1, X)):
        B[i] += A[i][j]


if X % 2:
    for i in range(X, N+1):
        B[i] += 1


for i in range(1, X):
    a = X - 1 - 2 * i
    if a < 0: continue
    for j in range((a+1) // 2, a + 1):
        k = j + 2 * i
        if k > N: break
        B[k] += A[j][a]
        if B[k] >= P: B[k] -= P

ans = 0
for i, b in enumerate(B):
    ans = (ans + b * A[-1][-1-i]) % P

print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

"""
・累積和の到達地点集合ごとに見る
・type1：X未満で終わる
・type2：X+1以上2X未満
・type3：2X以上、これはXが奇数の場合のみ
"""

MOD = 998244353

N,X = map(int,read().split())

def cumprod(arr,MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U,MOD):
    x = np.arange(U,dtype=np.int64); x[0] = 1
    fact = cumprod(x,MOD)
    x = np.arange(U,0,-1,dtype=np.int64); x[0] = pow(int(fact[-1]),MOD-2,MOD)
    fact_inv = cumprod(x,MOD)[::-1]
    return fact,fact_inv

U = N+N+100
fact,fact_inv = make_fact(U,MOD)
combN = fact[N] * fact_inv[:N+1] % MOD * fact_inv[N::-1] % MOD

def F1(N,X):
    
    def mult(P,Q):
        
        dP = len(P) - 1
        dQ = len(Q) - 1
        if dP < dQ:
            dP,dQ = dQ,dP
            P,Q = Q,P
        R = np.zeros(dP+dQ+1,np.int64)
        for n in range(dQ+1):
            R[n:n+dP+1] += Q[n] * P % MOD
        R %= MOD
        return R[:X]
    def power(P,n):
        if n == 0:
            return np.array([1],dtype=np.int64)
        Q = power(P,n//2)
        Q = mult(Q,Q)
        return mult(P,Q) if n&1 else Q
    P = np.array([1,1,1],np.int64)
    Q = power(P,N)
    return Q.sum() % MOD

def F2(N,X):
    x = np.zeros(N+1,np.int64)
    
    for n in range(X):
        m = (X-1) - (2+2*n)
        if m < 0:
            break
        
        two = np.arange(m//2+1,dtype=np.int64)
        one = m - 2*two
        coef = fact[one+two] * fact_inv[one] % MOD * fact_inv[two] % MOD
        rest = N-one-two-(2*n+2)
        ind = rest>=0
        rest = rest[ind]; coef = coef[ind]
        x[rest] += coef
    x %= MOD
    return (x * combN % MOD).sum() % MOD

def F3(N,X):
    
    if X%2 == 0:
        return 0
    if X > N:
        return 0
    n = N-X+1
    return combN[:n].sum() % MOD

answer = (F1(N,X) + F2(N,X) + F3(N,X)) % MOD
print(answer)