Elearning CodePath – CTP Online Judge

Yet Another DSU Problem

A36

🟢 Medium #DSU

# Steve's Blocks

**Problem ID:** UVa 98353

## Problem Description

Steve has a permutation **p** and an array **c**, both of length **n**. Steve wishes to sort the permutation **p** in a physics-based way using colored sand blocks called "gravity sort".

Namely, to perform gravity sort on **p**, Steve will do the following:

- For all **i** such that **1 ≤ i ≤ n**, place a sand block of color **c[i]** in position **(i, j)** for all **j** where **1 ≤ j ≤ p[i]**. Here, position **(x, y)** denotes a cell in the **x**-th row from the top and **y**-th column from the left.
- Apply downwards gravity to the array, so that all sand blocks fall as long as they can fall.

## Task

Alex looks at Steve's sand blocks after performing gravity sort and wonders how many pairs of arrays **(p', c')** where **p'** is a permutation would have resulted in the same layout of sand. Note that the original pair of arrays **(p, c)** will always be counted.

Please calculate this for Alex. As this number could be large, output it modulo **998 244 353**.

## Input Specification

The first line contains an integer **t** (**1 ≤ t ≤ 10⁴**) — the number of test cases.

The first line of each test case contains an integer **n** (**1 ≤ n ≤ 2 · 10⁵**) — the lengths of the arrays.

The second line of each test case contains **n** distinct integers **p₁, p₂, ..., pₙ** (**1 ≤ pᵢ ≤ n**) — the elements of **p**.

The following line contains **n** integers **c₁, c₂, ..., cₙ** (**1 ≤ cᵢ ≤ n**) — the elements of **c**.

The sum of **n** across all test cases does not exceed **2 · 10⁶**.

## Output Specification

For each test case, output the number of pairs of arrays **(p', c')** Steve could have started with, modulo **998 244 353**.

## Notes

- A permutation of length **n** is an array consisting of **n** distinct integers from **1** to **n** in arbitrary order. For example, **[2, 3, 1, 5, 4]** is a permutation, but **[1, 2, 2]** is not a permutation (2 appears twice in the array), and **[1, 3, 4]** is also not a permutation (**n = 3** but there is a **4** in the array).

---

## Solution Approach

This problem requires understanding gravity sort and counting distinct permutations that produce the same final configuration.

Key observations:
1. After gravity sort, blocks fall to the lowest available position in their respective columns
2. Two different **(p, c)** pairs can result in the same final layout
3. We need to count all such pairs that produce the same layout as the given input

The solution involves:
- Simulating the gravity sort process for the input
- Identifying which permutations could produce this same final configuration
- Using combinatorial counting based on the constraints imposed by column heights and block colors

✅ Đã AC: 0 / 0 submissions