Background

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

Problem Description

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:

#include "ascend.h"

Contestants need to implement the following function in the submitted source file ascend.cpp:

int ascend(int c, int n, int m, std::vector<int> p, std::vector<int> 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:

g++ grader.cpp ascend.cpp -o ascend -O2 -std=c++14 -static

Input Format

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}$.

Output Format

• 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.

0 1
3 6
0 2 0
2 3

1

Hint

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