Identify the Operations (Codeforces 1443F)
Tags: Greedy, combinatorics

We start with a permutation $$$a_1, a_2, \ldots, a_n$$$ and with an empty array $$$b$$$. We apply the following operation $$$k$$$ times.On the $$$i$$$-th iteration, we select an index $$$t_i$$$ ($$$1 \le t_i \le n-i+1$$$), remove $$$a_{t_i}$$$ from the array, and append one of the numbers $$$a_{t_i-1}$$$ or $$$a_{t_i+1}$$$ (if $$$t_i-1$$$ or $$$t_i+1$$$ are within the array bounds) to the right end of the array $$$b$$$. Then we move elements $$$a_{t_i+1}, \ldots, a_n$$$ to the left in order to fill in the empty space.You are given the initial permutation $$$a_1, a_2, \ldots, a_n$$$ and the resulting array $$$b_1, b_2, \ldots, b_k$$$. All elements of an array $$$b$$$ are distinct. Calculate the number of possible sequences of indices $$$t_1, t_2, \ldots, t_k$$$ modulo $$$998\,244\,353$$$.

Input: Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 100\,000$$$), denoting the number of test cases, followed by a description of the test cases.The first line of each test case contains two integers $$$n, k$$$ ($$$1 \le k < n \le 200\,000$$$): sizes of arrays $$$a$$$ and $$$b$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$): elements of $$$a$$$. All elements of $$$a$$$ are distinct.The third line of each test case contains $$$k$$$ integers $$$b_1, b_2, \ldots, b_k$$$ ($$$1 \le b_i \le n$$$): elements of $$$b$$$. All elements of $$$b$$$ are distinct.The sum of all $$$n$$$ among all test cases is guaranteed to not exceed $$$200\,000$$$.

Output: For each test case print one integer: the number of possible sequences modulo $$$998\,244\,353$$$.

Note: $$$\require{cancel}$$$Let's denote as $$$a_1 a_2 \ldots \cancel{a_i} \underline{a_{i+1}} \ldots a_n \rightarrow a_1 a_2 \ldots a_{i-1} a_{i+1} \ldots a_{n-1}$$$ an operation over an element with index $$$i$$$: removal of element $$$a_i$$$ from array $$$a$$$ and appending element $$$a_{i+1}$$$ to array $$$b$$$.In the first example test, the following two options can be used to produce the given array $$$b$$$:  $$$1 2 \underline{3} \cancel{4} 5 \rightarrow 1 \underline{2} \cancel{3} 5 \rightarrow 1 \cancel{2} \underline{5} \rightarrow 1 2$$$; $$$(t_1, t_2, t_3) = (4, 3, 2)$$$;  $$$1 2 \underline{3} \cancel{4} 5 \rightarrow \cancel{1} \underline{2} 3 5 \rightarrow 2 \cancel{3} \underline{5} \rightarrow 1 5$$$; $$$(t_1, t_2, t_3) = (4, 1, 2)$$$. In the second example test, it is impossible to achieve the given array no matter the operations used. That's because, on the first application, we removed the element next to $$$4$$$, namely number $$$3$$$, which means that it couldn't be added to array $$$b$$$ on the second step.In the third example test, there are four options to achieve the given array $$$b$$$:  $$$1 4 \cancel{7} \underline{3} 6 2 5 \rightarrow 1 4 3 \cancel{6} \underline{2} 5 \rightarrow \cancel{1} \underline{4} 3 2 5 \rightarrow 4 3 \cancel{2} \underline{5} \rightarrow 4 3 5$$$; $$$1 4 \cancel{7} \underline{3} 6 2 5 \rightarrow 1 4 3 \cancel{6} \underline{2} 5 \rightarrow 1 \underline{4} \cancel{3} 2 5 \rightarrow 1 4 \cancel{2} \underline{5} \rightarrow 1 4 5$$$; $$$1 4 7 \underline{3} \cancel{6} 2 5 \rightarrow 1 4 7 \cancel{3} \underline{2} 5 \rightarrow \cancel{1} \underline{4} 7 2 5 \rightarrow 4 7 \cancel{2} \underline{5} \rightarrow 4 7 5$$$; $$$1 4 7 \underline{3} \cancel{6} 2 5 \rightarrow 1 4 7 \cancel{3} \underline{2} 5 \rightarrow 1 \underline{4} \cancel{7} 2 5 \rightarrow 1 4 \cancel{2} \underline{5} \rightarrow 1 4 5$$$;

Sample Inputs:
3
5 3
1 2 3 4 5
3 2 5
4 3
4 3 2 1
4 3 1
7 4
1 4 7 3 6 2 5
3 2 4 5

Sample Outputs:
2
0
4

Solution (Python):
import sys
input = sys.stdin.readline
R = lambda : map(int, input().split())
mod = 998244353
(t,) = R()
for _ in [0] * t:
    (n, k) = R()
    a = tuple(R())
    b = tuple(R())
    vis = {i: 1 for i in range(n + 1)}
    vis[0] = vis[n + 1] = 0
    pos = {a: i for (i, a) in enumerate(a, 1)}
    ans = 0
    for i in b:
        vis[pos[i]] = 0
    for i in b:
        if vis[pos[i] - 1] == 0 and vis[pos[i] + 1] == 0:
            ans = -1
            break
        if vis[pos[i] - 1] == 1 and vis[pos[i] + 1] == 1:
            ans += 1
        vis[pos[i]] = 1
    if ans != -1:
        print(pow(2, ans, mod))
    else:
        print(0)

Solution (Python):
q = 998244353
ans = []
for _ in range(int(input())):
    (n, k) = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    pos = {a: i for (i, a) in enumerate(A, 1)}
    u = {i: 0 for i in range(1, n + 1)}
    for b in B:
        u[pos[b]] = 1
    u[0] = u[n + 1] = 1
    cnt = 0
    for b in B:
        cur = 2 - u[pos[b] - 1] - u[pos[b] + 1]
        if not cur:
            ans.append(0)
            break
        elif cur == 2:
            cnt += 1
        u[pos[b]] = 0
    else:
        ans.append(pow(2, cnt, q))
print(*ans, sep='\n')

Solution (Python):
mod = 998244353
for _ in range(int(input())):
    (N, K) = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    pos = {a: i for (i, a) in enumerate(A, 1)}
    seen = {i: 0 for i in range(1, N + 1)}
    for b in B:
        seen[pos[b]] = 1
    seen[0] = seen[N + 1] = 1
    cnt = 0
    for b in B:
        cur = 2 - seen[pos[b] - 1] - seen[pos[b] + 1]
        if not cur:
            print(0)
            break
        elif cur == 2:
            cnt += 1
        seen[pos[b]] = 0
    else:
        print(pow(2, cnt, mod))