题目描述

给定一个长度为 $n$ 的排列 $p$ 和一个长度为 $n$ 的颜色数组 $c$。我们要对排列 $p$ 进行一种叫做“重力排序”的操作。

重力排序过程：
1. 想象一个二维网格。对于每个 $i$（从 1 到 $n$），在第 $i$ 列，我们垂直堆叠 $p_i$ 个颜色为 $c_i$ 的沙块。具体地，在位置 $(i, j)$ 放置沙块，其中 $1 \le j \le p_i$。这里 $(x, y)$ 表示第 $x$ 行（从上到下）第 $y$ 列（从左到右）的单元格。
2. 然后，对整个网格施加向下的重力。所有沙块会尽可能地向下掉落，直到它们下方有一个沙块或者到达第一行。

重力排序完成后，沙块会形成一个新的布局。

问题：
计算有多少对不同的初始数组 $(p’, c’)$（其中 $p’$ 必须是 $1$ 到 $n$ 的一个排列）能够通过上述重力排序过程，产生与原始输入 $(p, c)$ 完全相同的最终沙块布局。

注意：原始的 $(p, c)$ 对自身也算作一个有效的对。
结果需要对 $998244353$ 取模。

$^*$ 一个长度为 $n$ 的排列是指包含从 $1$ 到 $n$ 的 $n$ 个不同整数的任意顺序数组。

样例

输入:
4
1
1
1
5
5 3 4 1 2
1 1 1 1 1
5
4 2 3 1 5
2 1 4 1 5
40
... (省略)
... (省略)

输出:
1
120
1
143654893

样例解释

• 样例 2: $p = [5, 3, 4, 1, 2]$, $c = [1, 1, 1, 1, 1]$。所有沙块颜色相同。重力排序后，列的高度会变成 $1, 2, 3, 4, 5$。因为所有颜色都是 1，任何初始排列 $p’$（只要是 $1..5$ 的排列）都会产生同样高度（$1..5$）且颜色全为 1 的最终布局。因此，有 $5! = 120$ 种可能的 $p’$。对于每种 $p’$， $c’$ 必须是 $[1, 1, 1, 1, 1]$。总数为 120。
• 样例 3: $p = [4, 2, 3, 1, 5]$, $c = [2, 1, 4, 1, 5]$。可以证明只有原始的 $(p, c)$ 能产生图示的最终布局。答案为 1。

算法 (并查集 + 模拟/贪心)

$O(N \alpha(N))$

思路分析

1. 理解重力排序的最终状态:

   • 重力排序的关键在于，它将初始列的高度进行排序。如果初始排列是 $p = [p_1, p_2, \dots, p_n]$，那么重力排序后，最终布局的列高度将是 $p$ 中所有元素的排序结果。
   • 由于 $p$ 是 $1$ 到 $n$ 的一个排列，其排序结果必然是 $1, 2, 3, \dots, n$。也就是说，最终布局中，第 $j$ 列的高度恰好是 $j$ (假设列是从左到右按高度排序的，或者我们直接说最终的 $n$ 列高度集合是 $\{1, 2, \dots, n\}$)。
   • 重要的是沙块的 颜色 和 最终位置。重力只改变沙块的垂直位置（行号），不改变其水平位置（列号）。

2. 什么决定了最终布局:

   • 最终的列高度集合总是 $\{1, 2, \dots, n\}$，只要初始 $p’$ 是一个排列。
   • 最终布局的颜色模式取决于初始的 $(p’, c’)$。如果两个不同的初始对 $(p, c)$ 和 $(p’, c’)$ 产生相同的最终布局，那么不仅最终高度集合要相同（这总是满足的），而且在每个最终位置 $(x, y)$ 的沙块颜色也必须相同。

3. 寻找等价条件:

   • 什么时候两个初始对 $(p, c)$ 和 $(p’, c’)$ 会产生相同的最终布局？
   • 考虑最终布局。设最终列 $j$ 的高度为 $h_j$（我们知道 $h_j = j$），最终位置 $(x, j)$ 的颜色为 $C(x, j)$。
   • 关键在于理解初始列和最终列的关系。一个初始在第 $i$ 列、高度为 $k$（即在 $(k, i)$ 位置）的沙块，最终会落到第 $j$ 列的某个位置 $(x, j)$。
   • 重要性质: 考虑所有初始高度为 $H$ 的列。设这些列的索引集合为 $I_H = \{i \mid p[i] = H\}$，它们的颜色集合为 $Colors_H = \{c[i] \mid i \in I_H\}$（这是一个多重集）。在最终布局中，所有位于精确高度 $H$ 的沙块（即位置 $(H, j)$ 其中 $j \ge H$）必然来自初始高度为 $H$ 的这些列。并且，最终布局中在高度 $H$ 的这些沙块的颜色集合 $\{C(H, j) \mid j \ge H\}$ 必须与初始颜色多重集 $Colors_H$ 完全相同。
   • 由于 $p$ 是一个排列，对于每个高度 $H \in \{1, \dots, n\}$，只有一个索引 $i_H$ 使得 $p[i_H] = H$。因此，$Colors_H$ 只包含一个颜色 $c[i_H]$。
   • 这意味着，对于任何产生相同最终布局的 $(p’, c’)$，必须满足：对于每一个高度 $H$，设 $i’_H$ 是唯一使得 $p’[i’_H] = H$ 的索引，那么必须有 $c’[i’_H] = c[i_H]$。
   • 换句话说，与特定高度 $H$ 相关联的颜色必须是固定的，这个颜色由原始的 $(p, c)$ 对唯一确定。令 $ColorForHeight(H) = c[i_H]$。
   • 对于任何合法的 $(p’, c’)$ 对，必须满足 $c’[i] = ColorForHeight(p’[i])$ 对所有 $i$ 成立。

4. 计数问题:

   • 现在问题转化为：有多少个排列 $p’$，使得当按照 $c’[i] = ColorForHeight(p’[i])$ 定义 $c’$ 时，产生的最终布局与原始 $(p, c)$ 相同？
   • 我们已经知道，只要 $p’$ 是排列，最终高度总是 $1..n$。颜色约束 $c’[i] = ColorForHeight(p’[i])$ 保证了每个高度 $H$ 对应的颜色是正确的。那么还需要什么条件？
   • 似乎任何满足 $c’[i] = ColorForHeight(p’[i])$ 的排列 $p’$ 都应该产生正确的最终布局。
   • 但是，$(p’, c’)$ 本身必须是一个合法的输入对吗？题目没有说 $c’$ 必须与输入的 $c$ 有直接关系，而是问有多少对 $(p’, c’)$。我们的推导表明，对于给定的 $p’$， $c’$ 是唯一确定的：$c’[i] = ColorForHeight(p’[i])$。
   • 所以，问题简化为：有多少个排列 $p’$，使得由它确定的 $c’$（即 $c’[i] = ColorForHeight(p’[i])$）与 $p’$ 一起，能生成目标最终布局？
   • 这个条件似乎对 $p’$ 没有额外的约束！只要 $p’$ 是 $1..n$ 的排列，它就能生成正确的高度，并且相应的 $c’$ 保证了正确的颜色。
   • 这是否意味着答案总是 $n!$？样例 3 ($p=[4,2,3,1,5], c=[2,1,4,1,5]$) 的答案是 1，说明肯定有其他约束。

5. 重新审视重力排序和颜色:

   • 重力排序实际上是对初始列进行稳定排序。如果两个初始列 $i_1$ 和 $i_2$ 有相同的高度 $p[i_1] = p[i_2]$，它们在最终布局中的相对水平顺序（假设它们落到了最终列 $j_1, j_2$）与它们的初始相对顺序 $i_1$ vs $i_2$ 相同。
   • 但是 $p$ 是一个排列，所以没有相同的高度。
   • 让我们看看代码的逻辑。它似乎在模拟一个过程，每次移除一个值，并根据颜色合并相邻的“可用”索引。

6. 代码逻辑详解:

   • p[x] = i: 预处理，方便根据值 x+1 快速找到它在输入 p_in 中的索引 i。
   • DSU dsu(n): 并查集作用在索引 $0..n-1$ 上。
   • Initial merges: if (i && c[i] == c[i - 1]) dsu.merge(i, i - 1); 将初始数组中相邻且颜色相同的索引合并到同一个集合中。这意味着一个 DSU 集合代表了一个连续的、颜色相同的索引块。
   • l, r: 维护一个概念上的双向链表，表示当前尚未被处理的索引。l[i] 是 i 左边的未处理索引，r[i] 是 i 右边的未处理索引。
   • ans = 1: 初始化答案。
   • for (auto x : p): 这个循环的迭代顺序很关键。p 存储的是 value-1 -> index 的映射。for (auto x : p) 实际是在遍历 x 从 0 到 n-1。在第 x 次迭代中，它处理的是值为 x+1 的那个元素。所以，循环是按值从小到大 (1 to n) 的顺序处理的。
   • idx = p[x]: 获取值为 x+1 的元素在原始输入中的索引 idx。
   • ans *= dsu.size(idx): 查找 idx 所在的 DSU 集合（代表一个当前连续的、颜色相同的、且包含 idx 的未处理索引块）。将答案乘以这个集合的大小。
   • dsu.siz[dsu.find(idx)]--: 将这个集合的大小减 1。这代表我们已经为值 x+1 “分配” 了这个集合中的一个位置。
   • Linked list update: 从链表中移除 idx。获取 idx 原来的左右邻居 a 和 b。
   • Merging neighbors: if (a != -1 && b != -1 && c[a] == c[b]) dsu.merge(a, b); 如果移除 idx 使得原本不相邻的 a 和 b 变得相邻了，并且它们的颜色相同，那么将它们所在的 DSU 集合合并。这表示 a 和 b 现在属于同一个连续的、颜色相同的、未处理的索引块。

7. 算法的含义:

   • 这个算法在模拟构建一个合法的排列 $p’$。它按值 $h=1, 2, \dots, n$ 的顺序决定将值 $h$ 放在哪个初始索引 $i$ 上（即确定 $p’[i]=h$）。
   • 当考虑值 $h$ 时，我们知道它必须来自原始索引 idx = p[h-1]，并且具有颜色 C = c[idx]。
   • 我们要将这个 “值 $h$，颜色 $C$” 的任务分配给一个当前可用的初始索引 $j$。
   • 哪些索引 $j$ 是可用的？是那些尚未被分配值的索引。
   • 哪个可用索引 $j$ 可以被分配值 $h$？为了保持最终颜色模式不变，分配给值 $h$ 的索引 $j$ (即 $p’[j]=h$) 必须满足 $c’[j]=C$。但 $c’[j]$ 是由 $p’[j]=h$ 决定的，即 $c’[j]=ColorForHeight(h)=C$。这个颜色条件总是满足的！
   • 关键在于初始 DSU 和后续的合并。DSU 维护的是当前可用且颜色相同的连续索引块。
   • 当我们要为值 $h$ (来自原始索引 idx，颜色 C) 选择一个目标位置 j 时，这个目标位置 j 必须属于当前包含 idx 的那个 DSU 集合（颜色相同的连续可用块）。
   • dsu.size(idx) 就是当前有多少个这样的可用位置可供选择。因为任何一个这样的位置 j 被选中（设 $p’[j]=h$），其颜色 $c’[j]$ 都会被设为 $C$，这与原始配置一致。
   • 我们有 dsu.size(idx) 种选择来放置值 $h$。每种选择对应一种不同的 $p’$。
   • 将大小减 1 表示这个 DSU 集合中的一个位置被用掉了。
   • 合并邻居确保了如果移除一个索引使得两个同色块相邻，它们会合并成一个更大的选择池。
   • 这个过程利用乘法原理计算了所有可能的、能产生相同最终颜色布局的排列 $p’$ 的数量。

时间复杂度

• 预处理 p 数组: $O(N)$。
• 初始化 DSU: $O(N)$。
• 初始 DSU 合并: 最多 $N-1$ 次 merge，总共 $O(N \alpha(N))$。
• 初始化链表: $O(N)$。
• 主循环: $N$ 次迭代。
  • 内部操作：DSU find/size ($O(\alpha(N))$), 链表操作 ($O(1)$), DSU merge ($O(\alpha(N))$)。
• 总时间复杂度: $O(N \alpha(N))$，其中 $\alpha$ 是反阿克曼函数，非常接近常数。可以认为是近似线性的 $O(N)$。

空间复杂度

• 存储 p, c, l, r: $O(N)$。
• DSU 结构: $O(N)$。
• 总空间复杂度: $O(N)$。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

// 定义常用类型别名
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;
using i128 = __int128;

// 并查集 (Disjoint Set Union) 结构体
struct DSU {
    std::vector<int> f, siz; // f: 父节点数组, siz: 集合大小数组

    DSU() {} // 默认构造函数
    DSU(int n) { // 带大小的构造函数
        init(n);
    }

    // 初始化并查集，大小为 n
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0); // 初始化父节点为自己 (0, 1, ..., n-1)
        siz.assign(n, 1); // 初始化每个集合大小为 1
    }

    // 查找元素 x 所在集合的根节点 (带路径压缩)
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]]; // 路径压缩
        }
        return x;
    }

    // 判断 x 和 y 是否在同一个集合
    bool same(int x, int y) {
        return find(x) == find(y);
    }

    // 合并 x 和 y 所在的集合 (按大小合并 - 代码中未显式按大小，但会影响效率)
    // 返回 true 如果成功合并, false 如果已在同一集合
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false; // 已经在同一集合
        }
        // 将 y 合并到 x (没有按大小优化)
        siz[x] += siz[y]; // 更新 x 的大小
        f[y] = x; // 将 y 的根指向 x
        return true;
    }

    // 返回元素 x 所在集合的大小
    int size(int x) {
        return siz[find(x)];
    }
};

// ... [省略了 ModInt 模板代码] ...
// Z 是 ModInt<998244353> 的别名

using Z = ModInt<998244353>; // 使用模整数类型

// 解决单个测试用例的函数
void solve() {
    int n; // 数组长度
    std::cin >> n;

    // l, r 数组模拟双向链表，存储每个索引的左、右邻居索引
    // -1 表示没有邻居 (边界)
    std::vector<int> l(n), r(n);
    for (int i = 0; i < n; i++) {
        l[i] = i - 1; // 左邻居是 i-1
        r[i] = i + 1; // 右邻居是 i+1
    }
    r[n - 1] = -1; // 最后一个元素的右邻居是 -1

    // p 数组存储 值 -> 索引 的映射 (0-based)
    // p[x] = i 表示原始排列中值为 x+1 的元素位于索引 i
    std::vector<int> p(n);
    for (int i = 0; i < n; i++) {
        int x; // 读入原始排列的第 i 个元素
        std::cin >> x;
        x--; // 转换为 0-based 值
        p[x] = i; // 记录值 x 对应的索引是 i
    }

    std::vector<int> c(n); // 存储颜色数组 (0-based 索引)
    DSU dsu(n); // 初始化作用在索引上的并查集
    for (int i = 0; i < n; i++) {
        std::cin >> c[i]; // 读入颜色
        // 初始化 DSU：如果当前颜色与左边颜色相同，则合并它们的索引集合
        if (i && c[i] == c[i - 1]) {
            dsu.merge(i, i - 1);
        }
    }

    Z ans = 1; // 初始化答案为 1 (使用模整数类型 Z)
    // 遍历值 x 从 0 到 n-1 (对应原始值 1 到 n)
    for (auto x : p) { // 注意：这里的 `x` 实际上是 *索引* `idx`，循环顺序由 `p` 决定
                       // `p` 的内容是 0 到 n-1 的排列，所以这里是按某种顺序遍历索引
                       // 让我们纠正一下理解： `p` 的索引是 `val-1`，值是 `idx`
                       // 所以 `for (auto x : p)` 是错误的，应该是 `for (int x = 0; x < n; x++)`
                       // 然后 `int idx = p[x];`
                       // 修正后的理解：代码中的 `for (auto x : p)` 遍历的是 `p` 数组的值，
                       // 即它遍历的是原始输入 `p_in` 中 1 到 n 对应的 *索引*。
                       // 迭代的顺序是 `p[0], p[1], ..., p[n-1]`，即按 `val-1` 的顺序获取 `idx`。
                       // 这正是我们需要的：按值 1 到 n 的顺序处理。
        // x 现在代表的是值 val=i+1 在原始排列中的索引 (i 从 0 到 n-1)
        // 查找 x 所在 DSU 集合的根
        int root = dsu.find(x);
        // 将当前集合的大小（即放置值 val 的可用位置数）乘入答案
        ans *= dsu.size(root);
        // 将该集合的大小减 1，表示用掉了一个位置
        dsu.siz[root]--; // 直接修改根的大小

        // 从模拟链表中 "移除" 索引 x
        int a = l[x]; // 获取 x 的左邻居
        int b = r[x]; // 获取 x 的右邻居
        // 更新左邻居的右指针
        if (a != -1) {
            r[a] = b;
        }
        // 更新右邻居的左指针
        if (b != -1) {
            l[b] = a;
        }

        // 检查移除 x 后，原来的邻居 a 和 b 是否变得相邻，并且颜色相同
        if (a != -1 && b != -1 && c[a] == c[b]) {
            // 如果是，则合并 a 和 b 所在的 DSU 集合
            dsu.merge(a, b);
        }
    }
    // 输出最终答案
    std::cout << ans << "\n";
}

// 主函数
int main() {
    // 加速 IO
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t; // 测试用例数量
    std::cin >> t;

    // 处理每个测试用例
    while (t--) {
        solve(); // 调用解决函数
    }

    return 0; // 程序正常结束
}