P4993 Scoring System

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

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

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

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

**[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