#PQJ110x341. QOJ 110_341
QOJ 110_341
2016 年全国青少年信息学奥林匹克竞赛吉林省队选拔 第一试 成绩比较 成绩比较 【问题背景】 THU 的G 系中有许许多多的大牛,比如小R 的室友B 神。B 神已经厌倦了 与其他同学比较GPA(Grade Point Average,平均学分绩),他只在意G 系中有 多少同学被他“碾压”。 B 神声称,在G 系共有 𝑘 位同学被他碾压。 同是G 系大牛的D 神则认为B 神在吹牛,他查到了B 神每门必修课在G 系 的排名。他用了173 毫秒的时间就计算出了有多少种情况使得B 神所说的话成 立。现在他想考考聪明的你,看你是否也能求出这个情况数。 【问题描述】 G 系共有 𝑛 位同学,𝑚 门必修课。这 𝑛 位同学的编号为 0 到 𝑛−1 的 整数,其中B 神的编号为0 号。这 𝑚 门必修课编号为 0 到 𝑚−1 的整数。 一位同学在必修课 𝑖 上可以获得的分数是 1 到 𝑢𝑖 中的一个整数。 如果在每门课上A 获得的成绩均小于等于B 获得的成绩,则称A 被B 碾压。 在B 神的说法中,G 系共有 𝑘 位同学被他碾压(不包括他自己),而其他 𝑛−𝑘− 1 位同学则没有被他碾压。 D 神查到了B 神每门必修课的排名。这里的排名是指:如果B 神某门课的 排名为 𝑟,则表示有且仅有 𝑟−1 位同学这门课的分数大于B 神的分数,有且 仅有 𝑛−𝑟 位同学这门课的分数小于等于B 神(不包括他自己)。 我们需要求出全系所有同学每门必修课得分的情况数,使其既能满足B 神 的说法,也能符合D 神查到的排名。这里两种情况不同当且仅当有任意一位同 学在任意一门课上获得的分数不同。 你不需要像D 神那么厉害,你只需要计算出情况数模 109 + 7 的余数就可 以了。 【输入格式】 输入文件mark.in 的第一行包含三个正整数 𝑛, 𝑚, 𝑘,分别表示G 系的同学 数量(包括B 神),必修课的数量和被B 神碾压的同学数量。 第二行包含 𝑚 个正整数,依次表示每门课的最高分 𝑢𝑖。 第三行包含 𝑚 个正整数,依次表示B 神在每门课上的排名 𝑟𝑖。保证 1 ≤ 𝑟𝑖≤𝑛。 数据保证至少有 1 种情况使得B 神说的话成立。 【输出格式】 输出文件mark.out 仅一行一个正整数,表示满足条件的情况数模 109 + 7 的余数。
2016 年全国青少年信息学奥林匹克竞赛吉林省队选拔 第一试 成绩比较 【样例1 输入】 3 2 1 2 2 1 2 【样例1 输出】 10 【样例1 说明】 有且仅有以下10 种符合条件的情况: 编号 B 神 同学A 同学B 课程0 课程1 课程0 课程1 课程0 课程1 1 1 1 1 1 1 2 2 1 1 1 2 1 1 3 2 1 1 1 1 2 4 2 1 1 1 2 2 5 2 1 1 2 1 1 6 2 1 1 2 2 1 7 2 1 2 1 1 2 8 2 1 2 1 2 2 9 2 1 2 2 1 1 10 2 1 2 2 2 1 【样例2 输入】 5 3 2 4 3 2 2 1 2 【样例2 输出】 54096
2016 年全国青少年信息学奥林匹克竞赛吉林省队选拔 第一试 成绩比较 【子任务】 测试点编号 𝑛 𝑚 𝑢𝑖 1 ≤3 ≤3 ≤4 2 ≤3 ≤10 ≤100 3 ≤3 ≤100 ≤109 4,5 ≤5 ≤100 ≤109 6,7 ≤50 ≤50 ≤50 8~10 ≤100 ≤100 ≤109