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



Sample input:
3 3


Sample output:
14

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
MAX_K = 3000


def ceil(a: int, b: int)->int:
    '''a/b の切り上げを計算する。
    '''
    if (a // b) * b == a:
        return a//b
    return a//b + 1


# __fact[n] = n!
__fact = [0] * (MAX_K+1)
# __inv[n] = (n! の mod MOD に関する逆数)
__inv = [0] * (MAX_K+1)


def init_comb():
    # initialize __fact
    __fact[0] = 1
    __inv[0] = 1
    for n in range(MAX_K):
        __fact[n+1] = ((n+1) * __fact[n]) % MOD
        __inv[n+1] = mod_inv((n+1) * __fact[n], MOD)


def mod_inv(n: int, mod: int)->int:
    b, u, v = mod, 1, 0
    while b > 0:
        t = n // b

        n -= t * b
        u -= t * v

        n, b = b, n
        u, v = v, u

    return (u+mod) % mod


def comb(n: int, r: int)->int:
    '''nCr を計算する
    '''
    res = __fact[n]
    res = (res * __inv[n-r]) % MOD
    res = (res * __inv[r]) % MOD
    return res


def banned_x(N: int, X: int)->int:
    # 数列の全体の和を固定して調べる。
    # 数列の和の最大値は全て 2 でできている数列の 2*N
    res = 1  # 0 だけでできている分
    for S in range(1, 2*N+1):
        if S < X:
            # 1, 2 を合計で k 個利用するとする。
            # 1 を p 個、2 を q 個とすると
            # p+q=K; p+2q=S;
            # より
            # p=2K-S; q=S-K
            # となる。
            # このとき、0, 1, 2 の並べ方は
            # comb(N,p) * comb(N-p,q)
            # である。
            # また、0<=p; 0<=q より S/2<=k<=S が成り立つ。
            for k in range(ceil(S, 2), min(S, N)+1):
                p, q = 2*k - S, S-k
                res += comb(N, p) * comb(N-p, q)
                res %= MOD
        elif S == X:
            # nothing
            continue
        elif (S-X) & 1:
            # 2 を置かなければならない場所が [0, only2)
            # と (only2, N]
            only2 = (S-(X-1))//2

            # 1 が含まれない場合
            if 2*only2 >= X-1:
                if X & 1:
                    # 2 の置き方は N 個の位置から S//2 個
                    # 選ぶ組み合わせ。残りは 0 を置く
                    res += comb(N, S//2)
                    res %= MOD
            # 1 が含まれる場合
            else:
                # SS は 1,2 なんでも置いていいゾーンの幅
                SS = X-1-2*only2

                # k,p,q の変数の意味は S<X の時と同じ
                # ただし、2 は 2*only2 の領域にも置くので
                # 2 の個数は SS-k+2*only2 になり、
                # (N 個の位置から k+2*only2 個の位置を 1,2 用に確保)
                # x (k 個の位置から p 個の 1 を置く位置を確保)
                for k in range(ceil(SS, 2), min(N-2*only2, SS)+1):
                    p, q = 2*k-SS, SS-k
                    res += comb(N, k+2*only2) * comb(k, p)
                    res %= MOD
        # print('S={}, res={}'.format(S, res-tmp))

    return res


if __name__ == "__main__":
    N, X = map(int, input().split())

    init_comb()

    ans = banned_x(N, X)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
MAX_K = 3000


def ceil(a: int, b: int)->int:
    '''a/b の切り上げを計算する。
    '''
    if (a // b) * b == a:
        return a//b
    return a//b + 1


# __fact[n] = n!
__fact = [0] * (MAX_K+1)


def init_comb():
    # initialize __fact
    __fact[0] = 1
    for n in range(MAX_K):
        __fact[n+1] = ((n+1) * __fact[n]) % MOD


def mod_inv(n: int, mod: int)->int:
    b, u, v = mod, 1, 0
    while b > 0:
        t = n // b

        n -= t * b
        u -= t * v

        n, b = b, n
        u, v = v, u

    return (u+mod) % mod


def comb(n: int, r: int)->int:
    '''nCr を計算する
    '''
    res = __fact[n]
    res = (res * mod_inv(__fact[n-r], MOD)) % MOD
    res = (res * mod_inv(__fact[r], MOD)) % MOD
    return res


def banned_x(N: int, X: int)->int:
    # 数列の全体の和を固定して調べる。
    # 数列の和の最大値は全て 2 でできている数列の 2*N
    res = 1  # 0 だけでできている分
    for S in range(1, 2*N+1):
        tmp = res
        if S < X:
            # 1, 2 を合計で k 個利用するとする。
            # 1 を p 個、2 を q 個とすると
            # p+q=K; p+2q=S;
            # より
            # p=2K-S; q=S-K
            # となる。
            # このとき、0, 1, 2 の並べ方は
            # comb(N,p) * comb(N-p,q)
            # である。
            # また、0<=p; 0<=q より S/2<=k<=S が成り立つ。
            for k in range(ceil(S, 2), min(S, N)+1):
                p, q = 2*k - S, S-k
                res += comb(N, p) * comb(N-p, q)
                res %= MOD
        elif S == X:
            # nothing
            continue
        elif (S-X) & 1:
            # 2 を置かなければならない場所が [0, only2)
            # と (only2, N]
            only2 = (S-(X-1))//2

            # 1 が含まれない場合
            if 2*only2 >= X-1:
                if X & 1:
                    # 2 の置き方は N 個の位置から S//2 個
                    # 選ぶ組み合わせ。残りは 0 を置く
                    res += comb(N, S//2)
                    res %= MOD
            # 1 が含まれる場合
            else:
                # SS は 1,2 なんでも置いていいゾーンの幅
                SS = X-1-2*only2

                # k,p,q の変数の意味は S<X の時と同じ
                # ただし、2 は 2*only2 の領域にも置くので
                # 2 の個数は SS-k+2*only2 になり、
                # (N 個の位置から k+2*only2 個の位置を 1,2 用に確保)
                # x (k 個の位置から p 個の 1 を置く位置を確保)
                for k in range(ceil(SS, 2), min(N-2*only2, SS)+1):
                    p, q = 2*k-SS, SS-k
                    res += comb(N, k+2*only2) * comb(k, p)
                    res %= MOD
        # print('S={}, res={}'.format(S, res-tmp))

    return res


if __name__ == "__main__":
    N, X = map(int, input().split())

    init_comb()

    ans = banned_x(N, X)
    print(ans)

Submission status: Accepted

Solution code:

"""
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): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる)

    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

        #print (one,two,now)
        
        ans += now
        ans %= mod

print (ans)

Submission status: Accepted

Solution code:
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[i][j] is the number of permutations of 1's and 2's whose length is i and whose sum is j
A[0][0] = 1
B = [0] * (N + 1) # B[i] is the number of permutations of 1's and 2's with length i none of whose consecutive subsequenses is equal to X
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

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

# Type 2: Sum is 2X or more
if X % 2:
    for i in range(X, N+1):
        B[i] += 1

# Type 3: X <= Sum < 2X
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)

Submission status: Accepted

Solution code:
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):
    # 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)
    # X+1+2nで終わる場合
    for n in range(X):
        m = (X-1) - (2+2*n)
        if m < 0:
            break
        # 2+2n -> X-1に含まれる2の回数ごとに
        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):
    # 2X以上の偶数。Xは奇数で、+2を連打している場合
    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)

Submission status: Runtime Error

Solution code:
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+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):
    # 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):
    U = N+100
    fact,fact_inv = make_fact(U,MOD)
    combN = fact[N] * fact_inv[:N+1] % MOD * fact_inv[N::-1] % MOD
    x = np.zeros(N+1,np.int64)
    # X+1+2nで終わる場合
    for n in range(X):
        m = (X-1) - (2+2*n)
        if m < 0:
            break
        # 2+2n -> X-1に含まれる2の回数ごとに
        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):
    U = N+100
    fact,fact_inv = make_fact(U,MOD)
    combN = fact[N] * fact_inv[:N+1] % MOD * fact_inv[N::-1] % MOD
    # 2X以上の偶数。Xは奇数で、+2を連打している場合
    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)

Submission status: Runtime Error

Solution code:
//Pantyhose(black) + glasses = infinity

#include <bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int MAX_N = 3002;
const int MOD = 998244353;

int n, x;
int pw2[MAX_N], C[MAX_N][MAX_N], f[MAX_N][MAX_N*2], g[MAX_N][MAX_N];

void read_input() {
    cin >> n >> x;
}

//void NTT(vector<int> &a, bool invert) {
//    for (int i=0; i<n; ++i) {
//        if (rev_bit[i] > i)
//            swap(a[i], a[rev_bit[i]]);
//    }
//
//    int n = a.size();
//
//    for (int len=2; len<=n; len <<= 1) {
//        int wlen = invert ? ROOT : ROOT_1;
//        for (int i=len; i<=ROOT_PW; i <<= 1)
//            wlen = 1LL * wlen * wlen % MOD;
//
//        for (int i=0; i<n; i += len) {
//            int w = 1;
//            for (int j=0; j<len/2; ++j) {
//                int u = a[i+j], v = 1LL * a[i+j+len/2] * w % MOD;
//                a[i+j] = (u+v<MOD ? u + v : u + v - MOD);
//                a[i+j+len/2] = (u-v>=0 ? u - v : u - v + MOD);
//                w = 1LL * w * wlen % MOD;
//            }
//        }
//    }
//
//    if (invert) {
//        for (int i=0; i<n; ++i)
//            a[i] = 1LL * a[i] * inv[n] % MOD;
//    }
//}

void square(vector<int> &a) {
//    vector<int> fa(a.begin(), a.end());
//
//    int n = 1;
//
//    while (n<a.size())
//        n <<= 1;
//
//    fa.resize(n);
//    NTT(a, false);
//
//    for (int i=0; i<n; ++i)
//        fa[i] = 1LL * fa[i] * fa[i] % MOD;
//    NTT(fa, true);

    vector<int> res(a.size());

    for (int i=0; i<a.size(); ++i) {
        for (int j=0; i+j<a.size(); ++j) {
            res[i+j] = (res[i+j] + 1LL * a[i] * a[j]) % MOD;
        }
    }

    a = res;
}

void init() {
//    for (int i=0; i<=n*2; ++i)
//        inv[i] = pw(i, MOD-2);

    for (int i=0; i<=n; ++i)
        C[i][0] = C[i][i] = 1;

    for (int i=1; i<=n; ++i) {
        for (int j=1; j<i; ++j)
            C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD;
    }

    pw2[0] = 1;
    for (int i=1; i<=n; ++i)
        pw2[i] = pw2[i-1] * 2 % MOD;

    f[0][0] = 1;

    for (int l=1; l<=n; ++l) {
        for (int s=0; s<=x; ++s) {
            f[l][s] = f[l-1][s];
            if (s>=1)
                f[l][s] = (f[l][s] + f[l-1][s-1]) % MOD;
            if (s>=2)
                f[l][s] = (f[l][s] + f[l-1][s-2]) % MOD;
        }
    }
    // debug(f[n][2]);
}

int case1() {
    vector<int> h;

    for (int t=0; t<=x/2; ++t) {
        h.assign(n+1, 0);

        for (int l=0; l<=n; ++l) {
            if (l<=t)
                h[l] = pw2[l];
            else
                h[l] = (h[l-1] * 2 - C[l-1][t] + MOD) % MOD;
        }

        square(h);
        // if (t==1)
        //     PR0(h, n+1);

        for (int l=0; l<=n; ++l)
            g[l][t] = h[l];
    }
    // debug(g[2][1]);

    int res = 0;

    for (int l=0; n-l-2>=0; ++l) {
        for (int s=(x+1)%2; s+2<=x; s += 2) {
            // cerr << l << ' ' << s << ' ' << f[l][s] * g[n-l-2][(x-2-s)/2] << '\n';
            res = (res + 1LL * f[l][s] * g[n-l-2][(x-2-s)/2]) % MOD;
        }
    }

    if (x%2==0)
        res = (res + g[n-1][(x-1)/2]) % MOD;
    else
        res = (res + pw2[n]) % MOD;

    return res;
}

int case2() {
    int res = 0;

    for (int s=x%2; s<x; s += 2)
        res = (res + f[n][s]) % MOD;

    return res;
}

int main() {
	#ifdef GLASSES_GIRL
		freopen(FILE_NAME".in", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);

	read_input();
	init();
	// debug(case1());
    // debug(case2());
	cout << (case1() + case2()) % MOD;
}

Submission status: Runtime Error

Solution code:
a