题解

每次放入一个数以后，可以让它按小值模式或大值模式向上移动。我们知道放入的顺序和最后的数组，要数出有多少串模式选择能得到这个结果。即使两种模式都没交换，也要算作两种选择。

按正序模拟时，一次选择就可能改变后续操作遇到的数，很难只用一个状态概括。倒着考虑会方便很多。第 $n$ 次放入的数只可能出现在位置 $n$ 到根的路径上；把这次操作还原，就能继续处理第 $n-1$ 次。

小数据先枚举

子任务 1 中 $n\le18$，可以枚举全部 $2^n$ 串模式选择，逐一模拟，检查得到的数组是否与目标相同。每次上浮至多经过 $\lfloor\log_2 n\rfloor$ 条边，直接写的时间复杂度为 $O(2^n n\log n)$，空间复杂度为 $O(n)$。

搜索时也可以保留当前数组，记录本次交换过的位置，递归返回后按相反顺序交换回去，省掉重复模拟前缀的开销。两种模式即使得到相同数组，也必须分别搜索，因为题目统计的是选择序列。

这个做法通过子任务 1，得到 $20$ 分。

两种容易处理的性质

子任务 2 中所有数都相同，任意一次比较都不会交换。题目保证输入数组与目标数组包含相同的数，因此这里目标数组必然能得到。每一步都有两种模式，答案就是 $2^n\bmod998244353$。读入需要 $O(n)$ 时间，只计算答案时额外空间为 $O(1)$。配合小数据枚举，可以得到子任务 1、2 的 $30$ 分。

子任务 3 中，$v_i$ 比此前放入的数都大。选择小值模式，它留在位置 $i$；选择大值模式，它会一直走到根。逆序处理时，$v_i$ 的位置只可能是 $i$ 或 $1$。若在 $i$，删去它即可；若在根，就沿根到 $i$ 的路径把后面的数逐个向父位置搬回去，再删去位置 $i$；两处都找不到就无解。

这里每个数互不相同，所以 $i>1$ 时，两种模式会把 $v_i$ 放在不同位置，最后的状态能确定这一步选了哪种模式。只有第一次操作有两种选择。因此，只要逆推成功，答案就是 $2$。每次还原走一条长度为 $O(\log n)$ 的路径，总时间为 $O(n\log n)$，空间为 $O(n)$。结合前两种做法，可以通过子任务 1、2、3，得到 $40$ 分。

数互不相同时，位置已经确定

子任务 4 去掉了递增限制，但仍保证 $v_i$ 两两不同。逆序处理第 $i$ 步时，当前数组中的 $v_i$ 只有一个，它只能在位置 $i$ 到根的路径上。

沿这条路径寻找 $v_i$。若找不到，答案为 $0$；若找到了，就尝试把它移回位置 $i$，并检查这些交换是否符合某一种模式，以及它能否在找到的位置停止。下面会把这两个检查展开。

数互不相同时，发生交换的模式是唯一的；没有发生交换且 $i>1$ 时，父位置的数也不等于 $v_i$，仍只有一种模式能让它留下。因此合法目标的答案同样为 $2$，我们只需要判断逆推能否完成。

每步查找、检查和还原都只遍历这条路径，时间为 $O(n\log n)$，空间为 $O(n)$。这能通过子任务 3、4；和枚举、全相等的特判合用，可以得到前四个子任务的 $65$ 分。

重复值也能唯一还原

处理第 $i$ 步前，维护的数组是做完前 $i$ 次操作后的状态。记本次放入的数为 $x=v_i$。

假设它最后停在位置 $p$。从 $i$ 向上到 $p$ 的过程中，$x$ 每交换一次，就把父位置原有的数推到下面。于是操作结束后，路径上 $p$ 下方的数，恰好是这次与 $x$ 交换过的数。

这些数都不可能等于 $x$。小值模式只会越过严格大于 $x$ 的数，大值模式只会越过严格小于 $x$ 的数。只要遇到相等的数，上浮就会停止。

所以，从位置 $i$ 往根走，第一个满足 $a_p=x$ 的位置，一定就是本次放入的 $x$ 的停点。若要把更高处的另一个 $x$ 当作停点，下面这个相等的数就必须曾经与 $x$ 交换，与规则矛盾。路径外即使还有许多相等的数，也不会参与本次操作。

这就排除了重复值带来的歧义。沿路找不到 $x$ 时直接判无解；找到了以后，停点和需要还原的路径都确定了。

发生过交换时，检查整条路和停点

把路径记为

$$q_0=i,\quad q_1=\lfloor i/2\rfloor,\quad\ldots,\quad q_k=p.$$

当 $k>0$ 时，当前的 $a_{q_0}$ 是第一次与 $x$ 交换的数。若 $a_{q_0}>x$，本次只能选择小值模式；若 $a_{q_0}<x$，只能选择大值模式。由于 $p$ 是第一个等于 $x$ 的位置，这里不会相等。

随后要检查 $a_{q_0},a_{q_1},\ldots,a_{q_{k-1}}$ 是否都在 $x$ 的同一侧。小值模式要求它们全部严格大于 $x$，大值模式要求它们全部严格小于 $x$。不能只检查第一个数，否则可能把中途本来就应停止的上浮算进去。这里也不要求这些数彼此有序，只要求它们分别与 $x$ 的大小关系符合所选模式。

还要看 $p$ 的父位置。若 $p>1$，小值模式要求 $a_{\lfloor p/2\rfloor}\le x$，大值模式要求 $a_{\lfloor p/2\rfloor}\ge x$，这样才会在 $p$ 停下。等号是允许的。若这个检查不满足，即使一路交换都合法，$x$ 也会继续向上走，无法得到当前数组。$p=1$ 时没有父位置，不用检查。

检查通过后，前一个状态也确定了。把 $a_{q_k}$ 改成 $a_{q_{k-1}}$，再把 $a_{q_{k-1}}$ 改成 $a_{q_{k-2}}$，依次向下处理，最后删去位置 $q_0=i$。赋值要从靠近 $p$ 的地方开始，避免把还没读过的值覆盖。路径外的数保持原样。

这样还原出的数组重新插入 $x$，按确定的模式操作，会逐个发生我们检查过的交换，并在 $p$ 停下，恰好回到当前状态。所以这两个检查既不能省略，也已经足够。

没有交换时，两种模式可能都合法

若 $p=i$，说明 $x$ 放下后就没有移动，删掉位置 $i$ 即可。模式的数量取决于父位置的数。

若 $i=1$，两种模式都无事可做，贡献 $2$ 种。若 $i>1$ 且父位置的数也等于 $x$，两种模式同样都不交换，贡献 $2$ 种。父位置的数与 $x$ 不相等时，一种模式会交换，另一种会停止，只有停止的那种符合当前状态，贡献 $1$ 种。

发生过交换时，第一条交换已经确定了模式，所以贡献也只有 $1$ 种。

为什么这些数量可以直接相乘

每次逆推得到的前一个数组都是唯一的。即使某一步有两种合法模式，它们也都没有交换，删去新放入的数后得到的是同一个数组。我们不需要为这两种模式分别维护状态，后面要逆推的问题完全相同。

更具体地说，设当前状态有 $c_i$ 种合法的第 $i$ 步模式，且唯一还原出的前一个状态有 $F_{i-1}$ 种选择序列。每一种前缀序列都能接上这 $c_i$ 种模式，不同的前缀或最后一种模式也会产生不同的序列，所以

$$F_i=c_iF_{i-1}.$$

前面的讨论已经列出了全部可能的停点和模式。检查失败时没有合法前驱，答案为 $0$；检查通过时，所有合法序列都会还原到我们维护的那个前驱。一直逆推到空数组，而空数组对应唯一的空序列。于是从 $1$ 开始，把沿途的 $c_i$ 依次乘起来，就是要求的答案。

复杂度与实现

位置 $i$ 每向上走一步，编号至少减半，因此路径长度为 $O(\log i)$。查找、检查、还原各遍历这条路径一次，总时间复杂度为 $O(n\log n)$。两个数组占用 $O(n)$ 空间，临时路径只占 $O(\log n)$ 空间，总空间复杂度为 $O(n)$。

代码用循环变量 $i$ 表示当前有效数组的末尾。处理完这一步以后，后面只会访问编号不超过 $i-1$ 的位置，所以无需真的清空 $a_i$。答案每乘一次 $2$ 就取模。

这个做法通过全部子任务，得到 $100$ 分。

参考代码

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> v(n + 1), a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> v[i];
    for (int i = 1; i <= n; ++i) cin >> a[i];

    long long answer = 1;
    for (int i = n; i >= 1; --i) {
        int x = v[i], p = i;
        vector<int> path;
        // path 从下往上记录被 x 越过的位置，不含 x 的停点。
        while (p > 0 && a[p] != x) {
            path.push_back(p);
            p /= 2;
        }
        if (p == 0) {
            cout << 0 << '\n';
            return 0;
        }

        if (path.empty()) {
            if (p == 1 || a[p / 2] == x) answer = answer * 2 % MOD;
        } else {
            bool small = a[path[0]] > x;
            for (int t : path) {
                if (small ? a[t] <= x : a[t] >= x) {
                    cout << 0 << '\n';
                    return 0;
                }
            }
            // 既要能走到 p，也要确实停在 p。
            if (p > 1 && (small ? a[p / 2] > x : a[p / 2] < x)) {
                cout << 0 << '\n';
                return 0;
            }
            // 从靠近 p 的位置开始恢复，避免覆盖尚未使用的值。
            for (auto it = path.rbegin(); it != path.rend(); ++it) {
                a[*it / 2] = a[*it];
            }
        }
        // 位置 i 已被删除，后续只会访问 1 到 i - 1。
    }
    cout << answer << '\n';
    return 0;
}