AtCoder Beginner Contest 237 F

https://atcoder.jp/contests/abc237/tasks/abc237_f

これはDPですね。
数列が与えられたとき、数列の各要素までで最長の長さを考えると、例えば、3 1 4 2 3 5が与えられたとすると、

3 1 4 2 3 5
1 1 2 2 3 3

例えば、この数列に4を追加するとき、例えば先頭の3のとき長さ1ですが、あとに出てくる3の長さは3なので、4を追加したときに長さは4になります。なので、先頭の3は無視できます。つまり、最長だけ考えればよいので、

1 2 3 4 5
1 2 3 2 3

とすればよいです。これを状態と考えると、一つの数字に対して0～3が割り当てられるので、状態は2M bitで、32bit整数で表せます。上の状態だと、です。しかし、これだと状態数がで、遷移数がMあるので、計算量がとなって間に合いません。
しかし、例えば上の数列に6を追加したとき、4より5までの方が長いので4の長さに意味はないです。なので上の状態は、

1 2 3 4 5
1 2 3 3 3

と同じです。状態は単調増加でしかも1ずつしか上がりません。なので、状態数は3つ上がるなら個で、全部合わせてもとなり、計算量はとなります。

# coding: utf-8
# |LIS| = 3

from itertools import *
from collections import Counter


#################### library ####################

def read_tuple():
    return tuple(map(int, raw_input().split()))


#################### process ####################

def read_input():
    N, M = read_tuple()
    return (N, M)


def F(N, M):
    def to_list(s):
        return [ (s >> (2*k)) & 3 for k in range(M+1) ]
    
    def nexts(stat):
        new_stat = stat
        v = to_list(stat)
        for k in range(M, 0, -1):
            n = v[k]
            if v[k-1] == 3:
                continue
            elif n == v[k-1]:
                new_stat += 1 << (2*k)
                yield new_stat
            else:
                new_stat = stat
                yield new_stat
    
    def step(memo):
        new_memo = Counter()
        for stat, f in memo.items():
            for new_stat in nexts(stat):
                new_memo[new_stat] += f
        return dict((s, f % D) for s, f in new_memo.items())
    
    memo = { 0: 1 }
    for _ in range(N):
        memo = step(memo)
    
    return sum(f for s, f in memo.items() if ((s >> (2*M)) & 3) == 3) % D


#################### main ####################

D = 998244353
N, M = read_input()
print F(N, M)