Background

For Q&A, please go to: https://www.luogu.org/discuss/show?postid=79498.

Due to issues such as the time limit, please resubmit this problem once.

The time limit for this problem is set to 2 s.

Samples: https://files.cnblogs.com/files/ztz11/yl.rar.

---

As everyone knows, Luogu has a difficulty scoring system for problems. After solving a problem, users can choose the problem difficulty and algorithm tags to help improve Luogu's problemset.

(Original note: The following content is not real scoring data. It is made up by the author, for entertainment only.)

Problem Description

Student Menteur-Hxy is not very honest. In order to achieve the goal of getting AC on $100$ hard (black) problems before NOIp, he decided to hire some "water army" (paid voters), hiring at least $1$ of them.

Each paid voter has an ability value $x_i$, meaning this voter can solve problems with difficulty up to $x_i$ at most. These paid voters are very responsible: after solving the problem, they will always rate the problem as the highest difficulty. Of course, normal Luogu users will also solve problems and give normal ratings. Now, given all paid voters' ability values and the rating records from normal users for each problem, please find how many ways to choose paid voters such that the final rating of this problem becomes a black problem. Since the answer may be very large, output the number of ways $\bmod p$.

Scoring formula: remove one highest score and one lowest score, then take the average.

[Table 1: Voting Information]

Vote ID	Corresponding Difficulty	Score Contribution
$1$	Beginner	$1$
$2$	Junior-	$10$
$3$	Junior/Senior-	$15$
$4$	Junior+/Senior	$25$
$5$	Senior+/NOI Qualifier-	$40$
$6$	NOI Qualifier/NOI-	$55$
$7$	NOI	$75$
$8$	NOI+/CTSC	$100$

[Table 2: Difficulty Rules]

Difficulty Level	Color	Score Range
Beginner	Red	$1\sim 5$
Junior-	Orange	$6\sim 12$
Junior/Senior-	Yellow	$13\sim 20$
Junior+/Senior	Green	$21\sim 35$
Senior+/NOI Qualifier-	Blue	$36\sim 45$
NOI Qualifier/NOI-	Purple	$46\sim 70$
NOI+/CTSC	Black	$71\sim 100$

Input Format

This problem has multiple test cases.

The first line contains an integer $T$, the number of test cases.

For each test case:

• The first line contains three integers $n, m, p$, representing the number of paid voters hired by Menteur-Hxy, the number of ratings from Luogu users, and the modulus for output.
• The second line contains $n$ integers $s_1 \dots s_n$, where each $s_i$ is a paid voter's ability value.
• The third line contains $m$ integers $t_1 \dots t_n$, representing each Luogu user's vote ID.
• The fourth line contains an integer $k$, representing the difficulty coefficient of the problem.

Output Format

For each test case, output one integer per line: the total number of valid selection plans modulo $p$. If there is no solution, output $0$.

1
5 5 9
1 2 3 4 5
4 5 6 7 8
2

2

5
20 10 1329
540 499 490 419 308 261 323 476 476 374 23 13 14 16 19 34 43 19 27 32 
8 8 8 8 8 7 7 7 7 7 
50
20 10 1800
74 434 97 134 283 118 234 498 328 388 29 48 48 43 23 42 31 16 20 26 
8 8 7 6 8 8 8 7 7 7 
50
20 10 2704
142 378 330 281 377 64 340 309 466 289 34 37 19 17 20 48 21 28 38 15 
6 8 6 6 8 7 7 7 7 6 
50
20 10 72
365 356 456 479 459 222 548 377 212 223 38 20 49 18 49 38 31 48 41 17 
6 8 7 6 8 7 8 8 8 6 
50
20 10 1416
367 191 403 298 445 464 79 467 431 362 10 45 48 37 46 43 11 35 30 39 
8 6 8 7 7 7 8 8 7 8 
50

1023
1023
1023
15
1023

Hint

[Sample Explanation $1$]

The sum of Luogu users' scores is $25+40+55+75+100=295$. After discarding one lowest score, it becomes $270$. At this time, Menteur-Hxy can achieve the goal by hiring at least two paid voters.

Since there are $4$ paid voters who can solve this problem, the selection plans are:

$$\{1,2\}\{1,2,3\}\{1,2,3,4\}\{1,2,4\}\{1,3\}\{1,3,4\}\{1,4\}\{2,3\}\{2,3,4\}\{2,4\}\{3,4\}$$

There are $11$ plans in total, and $11 \bmod 9 = 2$.

[Constraints and Notes]

For $30\%$ of the testdata, $n, m \leq 50$.

For another $20\%$ of the testdata, $p$ is a prime.

For $100\%$ of the testdata, $1 \leq n, m, k,s_i \leq 10^5, 1 \leq t \leq 5, 2 \leq p \leq 3 \times 10^3, 1 \leq t_i \leq 8$.

It is guaranteed that the difference between the number of qualified paid voters and the minimum number of paid voters required does not exceed $5000$.

(Original note: This problem may be slightly tight on constant factors. Thanks to @Ghostcai and @Swhsz for helping to validate the problem.)

Translated by ChatGPT 5