luogu#P4993. 评分系统

    ID: 9017 远端评测题 2000ms 125MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>素数判断质数筛法递推枚举暴力

评分系统

题目背景

答疑请到:https://www.luogu.org/discuss/show?postid=79498

由于时限等问题,请大家重交一遍这道题

本题时限开至2s

样例:https://files.cnblogs.com/files/ztz11/yl.rar


众所周知,luogu 有题目难度的评分系统,用户在通过题目后可以选择题目难度以及算法标签,来完善 luogu 的题库。

(原注:以下内容非真实评分数据,纯属作者编造,仅供娱乐使用。)

题目描述

Menteur-Hxy 同学很不老实,为了实现 NOIp 前 AC 100100 道黑题的目标,他决定雇佣一些水军,最少雇佣 11 个水军。

每个水军都有一个能力值 xix_i,表示该水军可以解决难度最高为 xix_i 的题目。这些水军十分尽职尽责,在通过这道题目后都会给题目评最高难度。当然,luogu 的正常用户也会做题,他们会正常地评分。现在,我们给你所有水军的能力值以及每道题正常用户的评分记录,请你求出有多少种选择水军的方案,可以使这道题的评分变为黑题。因为答案可能过大,最终请输出答案数 modp\bmod p 的值。

评分计算公式:去掉一个最高分,去掉一个最低分后求平均分。

【表一:投票信息】

投票编号 对应难度 分数贡献
11 入门 11
22 普及- 1010
33 普及/提高- 1515
44 普及+/提高 2525
55 提高+/省选- 4040
66 省选/NOI- 5555
77 NOI 7575
88 NOI+/CTSC 100100

【表二:难度规则】

难度等级 对应颜色 对应分数
入门 151\sim 5
普及- 6126\sim 12
普及/提高- 132013\sim 20
普及+/提高 绿 213521\sim 35
提高+/省选- 364536\sim 45
省选/NOI- 467046\sim 70
NOI+/CTSC 7110071\sim 100

输入格式

本题有多组数据。

第一行,一个整数 TT,表示数据组数。

对于每组数据:

  • 第一行三个整数 n,m,pn, m, p,分别表示 Menteur-Hxy 找的水军数量,luogu 用户评分数量,和输出时的模数。
  • 第二行,nn 个整数 s1sns_1 \dots s_n 分别表示水军的能力值。
  • 第三行,mm 个整数 t1tnt_1 \dots t_n,表示每个 luogu 用户的投票编号。
  • 第四行,一个整数 kk ,表示题目的难度系数。

输出格式

对于每组数据,输出一行一个整数,表示总选择方案数对 pp 取模后的结果,如无解,则输出 00

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

提示

【样例解释 11

luogu 用户评分和为 25+40+55+75+100=29525+40+55+75+100=295,弃掉一个最低分后为 270270,这时 Menteur-Hxy 雇佣两个及以上水军就可以达到目的。

因为可以通过本题的水军共有 44 个,所以选择方案共有:

$$\{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\} $$

1111 种,对 99 取余后结果为 22

【数据规模与约定】

对于 30%30\% 的数据,n,m50n, m \leq 50

对于另外 20%20\% 的数据,pp 为质数。

对于 100%100\% 的数据,$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$。

保证合格水军的数量与需要的最少水军数量之差不超过 50005000

(原注:本题可能轻微卡常。感谢 @Ghostcai ,@Swhsz 帮忙验题。)