#P18931. [2026多校联测]观测窗口
[2026多校联测]观测窗口
观测窗口
题目描述
气象台把一天的观测结果按记录时间排成了一列。这一天共有 条记录,编号恰好是 到 ,每个编号只出现一次。第 条记录的编号为 ,质量分数为 。
工作人员准备从中截取一段连续的记录,作为一次观测的回放窗口。一个窗口可以只含一条记录,也可以包含全部记录。如果窗口内出现的编号恰好是一段连续的整数,就称它为完整窗口。编号在窗口内的排列顺序没有要求。
例如,编号依次为 的三条记录可以组成完整窗口,因为它们包含的编号恰好是 ;编号依次为 的两条记录不能组成完整窗口,因为缺少编号 。
一个窗口的分数是其中所有记录的质量分数之和,窗口的价值是这个分数的平方。请计算所有完整窗口的价值之和,并输出它除以 的余数。
两个窗口只要选取的起始位置或结束位置不同,就分别计算。
输入格式
第一行一个整数 。
第二行 个整数 ,表示记录的编号。
第三行 个整数 ,其中 是第二行第 条记录的质量分数。
输出格式
输出一个整数,表示所有完整窗口的价值之和除以 的余数。
样例 1 输入
4
2 1 4 3
1 2 3 4
样例 1 输出
188
样例 1 解释
四个只含一条记录的窗口都是完整窗口,价值之和为 。
另外三个完整窗口分别是位置 、 和 ,价值分别为 、、。因此答案为 。
样例 2 输入
3
3 2 1
0 1 0
样例 2 输出
4
样例 2 解释
任意一段连续记录都是完整窗口。含有第二条记录的四个窗口分数均为 ,其余窗口的分数为 ,所以答案为 。
样例 3
见下发目录中的 chronicle/3.in 和 chronicle/3.ans。
数据范围与子任务
对于所有测试数据,保证 , 是 到 的一个排列,。
各子任务独立整组计分,通过一组中的全部测试点才能获得该组分数,各组之间没有依赖关系。
| 子任务 | 分值 | 额外约束 |
|---|---|---|
| 1 | 20 | |
| 2 | 对所有 成立,或 对所有 成立 | |
| 3 | ||
| 4 | 40 | 无额外约束 |