luogu#P4993. 评分系统
评分系统
题目背景
答疑请到:https://www.luogu.org/discuss/show?postid=79498
由于时限等问题,请大家重交一遍这道题
本题时限开至2s
样例:https://files.cnblogs.com/files/ztz11/yl.rar
众所周知,luogu 有题目难度的评分系统,用户在通过题目后可以选择题目难度以及算法标签,来完善 luogu 的题库。
(原注:以下内容非真实评分数据,纯属作者编造,仅供娱乐使用。)
题目描述
Menteur-Hxy 同学很不老实,为了实现 NOIp 前 AC 道黑题的目标,他决定雇佣一些水军,最少雇佣 个水军。
每个水军都有一个能力值 ,表示该水军可以解决难度最高为 的题目。这些水军十分尽职尽责,在通过这道题目后都会给题目评最高难度。当然,luogu 的正常用户也会做题,他们会正常地评分。现在,我们给你所有水军的能力值以及每道题正常用户的评分记录,请你求出有多少种选择水军的方案,可以使这道题的评分变为黑题。因为答案可能过大,最终请输出答案数 的值。
评分计算公式:去掉一个最高分,去掉一个最低分后求平均分。
【表一:投票信息】
投票编号 | 对应难度 | 分数贡献 |
---|---|---|
入门 | ||
普及- | ||
普及/提高- | ||
普及+/提高 | ||
提高+/省选- | ||
省选/NOI- | ||
NOI | ||
NOI+/CTSC |
【表二:难度规则】
难度等级 | 对应颜色 | 对应分数 |
---|---|---|
入门 | 红 | |
普及- | 橙 | |
普及/提高- | 黄 | |
普及+/提高 | 绿 | |
提高+/省选- | 蓝 | |
省选/NOI- | 紫 | |
NOI+/CTSC | 黑 |
输入格式
本题有多组数据。
第一行,一个整数 ,表示数据组数。
对于每组数据:
- 第一行三个整数 ,分别表示 Menteur-Hxy 找的水军数量,luogu 用户评分数量,和输出时的模数。
- 第二行, 个整数 分别表示水军的能力值。
- 第三行, 个整数 ,表示每个 luogu 用户的投票编号。
- 第四行,一个整数 ,表示题目的难度系数。
输出格式
对于每组数据,输出一行一个整数,表示总选择方案数对 取模后的结果,如无解,则输出 。
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
提示
【样例解释 】
luogu 用户评分和为 ,弃掉一个最低分后为 ,这时 Menteur-Hxy 雇佣两个及以上水军就可以达到目的。
因为可以通过本题的水军共有 个,所以选择方案共有:
$$\{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\} $$共 种,对 取余后结果为 。
【数据规模与约定】
对于 的数据,。
对于另外 的数据, 为质数。
对于 的数据,$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$。
保证合格水军的数量与需要的最少水军数量之差不超过 。
(原注:本题可能轻微卡常。感谢 @Ghostcai ,@Swhsz 帮忙验题。)