P16433 [APIO 2026 China Region] Ascend

When submitting, please choose a language standard higher than C++17, and do not include the header file `ascend.h`.

Little N is a girl who likes things to be on an upward trend, because that often means good things are happening. Because of this hobby, for a permutation $q_1, q_2, \dots, q_n$ of $1 \sim n$, Little N also likes to study the positions where it rises. Specifically, she defines the set of all rising positions in permutation $q$ as $S(q) = \{1 \le i < n \mid q_i < q_{i+1}\}$. A rise is a lucky thing, but it is hard to measure exactly how lucky it is. So Little N decides to assign a weight to each position in the permutation to measure the lucky value. Specifically, she gives a non-negative integer sequence $w_1, w_2, \dots, w_{n-1}$, and defines the **lucky value** of permutation $q$ as $f(q) = \prod_{i \in S(q)} w_i$. In particular, if $S(q) = \varnothing$, then $f(q) = 1$. Little C is Little N’s good friend. One day, Little C gave her a lucky permutation $p_1, p_2, \dots, p_n$. But due to various accidents, some elements in the permutation were lost, and the values at those missing positions became $0$. After receiving the gift, Little N was not sad about the permutation being incomplete, because she was surprised to find that: **all elements at the non-missing positions in the permutation are still strictly increasing**, meaning that from left to right they form a strictly increasing subsequence. Little N immediately felt that she was the happiest girl in the world. At the same time, she was also curious about how lucky the original permutation given by Little C was. Therefore, she wants to compute the sum of $f(q)$ over all permutations $q$ that match $p$. A permutation $q$ matches $p$ if and only if: for all $1 \le i \le n$, we have $p_i = 0$ or $q_i = p_i$. Your task is to help Little N compute the sum of the lucky values $f(q)$ over all permutations $q$ that match $p$. ### Implementation Details Contestants do not need to, and should not, implement the `main` function. Contestants must ensure that the submitted program includes the header file `ascend.h`, i.e., add the following code at the beginning of the program: ```cpp #include "ascend.h" ``` Contestants need to implement the following function in the submitted source file `ascend.cpp`: ```cpp int ascend(int c, int n, int m, std::vector p, std::vector w); ``` * $c, n$ represent the test point ID and the length of the permutation, respectively. $c = 0$ indicates that this test point is the sample. * $p$ represents Little C’s permutation after some positions are missing. For $0 \le i < n$, $p_i$ is the value at position $i + 1$ in the permutation after missing. * $w$ represents Little N’s weight sequence. For $0 \le i < n - 1$, $w_i$ is the weight of position $i + 1$. * This function should return the sum of the lucky values $f(q)$ over all permutations $q$ that match $p$, modulo $m$. * For each test point, this function will be called by the grader exactly $t$ times. ### How to Run the Test Program Contestants can compile an executable program in this task directory using the following command: ```bash g++ grader.cpp ascend.cpp -o ascend -O2 -std=c++14 -static ```

For the compiled executable program: * The executable will read input from standard input in the following format: * The first line contains two non-negative integers $c, t$, representing the test point ID and the number of testdata groups. * Then follow the testdata groups. For each testdata group: * The first line contains two positive integers $n, m$. * The second line contains $n$ non-negative integers $p_1, p_2, \dots, p_n$. * The third line contains $n - 1$ non-negative integers $w_1, w_2, \dots, w_{n-1}$.

* The executable will output data to standard output in the following format: * For each testdata group, output one line with one non-negative integer, which is the return value of the `ascend` function.

### Sample 1 Explanation There are the following two permutations $q$ that match permutation $p$: 1. $q = [1, 2, 3], S(q) = \{1, 2\}, f(q) = w_1 \times w_2 = 2 \times 3 = 6$. 2. $q = [3, 2, 1], S(q) = \varnothing, f(q) = 1$. Therefore, the sum of the lucky values over all permutations that match $p$ is $6 + 1 = 7$, and the result modulo $m = 6$ is $1$. ### Constraints For all testdata, we have: * $1 \le t \le 5$. * $2 \le n \le 500$, $2 \le m \le 10^9$. * For all $1 \le i \le n$, $0 \le p_i \le n$. * All non-zero elements in sequence $p$ form a strictly increasing subsequence. * For all $1 \le i \le n-1$, $0 \le w_i < m$. ::cute-table{tuack} |Test Point ID|$n \le$|Special Property| |:-:|:-:|:-:| |$1,2$|$10$|None| |$3,4$|$20$|^ | |$5 \sim 7$|$500$|A| |$8 \sim 10$|$50$|B| |$11 \sim 13$|$150$| ^| |$14 \sim 18$|$500$| ^| |$19,20$| ^|None| - Special property A: For all $1 \le i \le n$, $p_i = 0$. - Special property B: $m \ge 5 \times 10^8$ and $m$ is prime. Translated by ChatGPT 5