#5741. 「APIO2026 中国区」上升

标签: 传统 | 时间限制: 3500 ms | 内存限制: 1024 MiB |

题目描述

小 N 是一个喜欢事物呈上升趋势的女孩子，因为这往往意味着好事发生！

正是因为这样的爱好，对于一个 $1 \sim n$ 的排列 $q_1, q_2, \dots, q_n$，小 N 也喜欢研究其上升的位置。具体地，她定义排列 $q$ 中所有上升的位置构成的集合为 $S(q) = \{1 \le i < n \mid q_i < q_{i+1}\}$。

上升是一件幸运的事情，但具体有多幸运却是难以量化的。于是小 N 决定给排列里的每一个位置赋权，从而去量化幸运值。具体地，她给出了一个非负整数序列 $w_1, w_2, \dots, w_{n-1}$，并定义排列 $q$ 的幸运值为 $f(q) = \prod_{i \in S(q)} w_i$。特别地，若 $S(q) = \varnothing$，则 $f(q) = 1$。

小 C 是小 N 的好朋友，有一天，小 C 送了一个幸运的排列 $p_1, p_2, \dots, p_n$ 给她。但由于种种意外，排列中有些位置的元素缺失了，这些缺失位置的值变成了 $0$。

收到礼物后，小 N 并没有为排列的不完整而感到难过，因为她惊奇地发现：排列中所有未缺失位置上的元素仍是单调递增的，即它们从左到右构成了一个单调递增的子序列。

小 N 顿时觉得自己是世界上最幸福的女孩子。同时，她也很好奇原来小 C 送的排列到底有多幸运。于是，她想要计算出符合 $p$ 的所有排列 $q$ 的幸运值 $f(q)$ 之和。其中排列 $q$ 符合 $p$ 当且仅当：对于所有 $1 \le i \le n$，均有 $p_i = 0$ 或 $q_i = p_i$。

你的任务是帮助小 N 求出，符合 $p$ 的所有排列 $q$ 的幸运值之和。

实现细节

选手不需要，也不应该实现 main 函数。

选手需要确保提交的程序包含头文件 ascend.h，即在程序开头加入以下代码：

#include "ascend.h"

选手需要在提交的程序源文件 ascend.cpp 中实现以下函数：

int ascend(int c, int n, int m, std::vector<int> p, std::vector<int> w);

• $c, n$ 分别表示测试点编号、排列的长度。$c = 0$ 表示该测试点为样例。
• $p$ 表示缺失了若干个位置后的小 C 的排列。对于 $0 \le i < n$，$p_i$ 表示缺失后的排列的第 $i + 1$ 位的值。
• $w$ 表示小 N 的权值序列。对于 $0 \le i < n - 1$，$w_i$ 表示第 $i + 1$ 个位置的权值。
• 该函数需要返回符合 $p$ 的所有排列 $q$ 的幸运值 $f(q)$ 之和对 $m$ 取模后的结果。
• 对于每个测试点，该函数会被交互库调用恰好 $t$ 次。

测试程序方式

选手可以在本题目录下使用如下命令编译得到可执行程序：

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

输入格式

对于编译得到的可执行程序：

• 可执行文件将从标准输入读入以下格式的数据：
  • 输入的第一行包含两个非负整数 $c, t$，分别表示测试点编号和测试数据组数。
  • 接下来依次为每组测试数据，对于每组测试数据：
    • 第一行包含两个正整数 $n, m$。
    • 第二行包含 $n$ 个非负整数 $p_1, p_2, \dots, p_n$。
    • 第三行包含 $n - 1$ 个非负整数 $w_1, w_2, \dots, w_{n-1}$。

输出格式

• 可执行文件将输出以下格式的数据至标准输出：
  • 对于每组测试数据，输出一行一个非负整数，表示 ascend 函数的返回值。

样例 1

输入

0 1
3 6
0 2 0
2 3

输出

1

共有以下两个排列 $q$ 符合排列 $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$。

因此，符合 $p$ 的所有排列的幸运值之和为 $6 + 1 = 7$，对 $m = 6$ 取模后的结果为 $1$。

数据范围

对于所有测试数据，均有：

• $1 \le t \le 5$;
• $2 \le n \le 500$, $2 \le m \le 10^9$;
• 对于所有 $1 \le i \le n$，均有 $0 \le p_i \le n$;
• 序列 $p$ 中所有不为 $0$ 的元素构成一个单调递增的子序列;
• 对于所有 $1 \le i \le n-1$，均有 $0 \le w_i < m$。

• 特殊性质 A：对于所有 $1 \le i \le n$，均有 $p_i = 0$。
• 特殊性质 B：$m \ge 5 \times 10^8$ 且 $m$ 为素数。