#1172. QOJ 30_5223
QOJ 30_5223
QOJ 30_5223
题目描述
NOI2016 浙江省队选拔赛第二试 线段树 线段树 【问题描述】 小Yuuka 遇到了一个题目:有一个序列 𝑎1, 𝑎2, ⋯, 𝑎𝑛, 𝑞 次操作,每次把一 个区间内的数改成区间内的最大值,问最后每个数是多少。小Yuuka 很快地就使 用了线段树解决了这个问题。 于是充满智慧的小Yuuka 想,如果操作是随机的,即在这 𝑞 次操作中每次等 概率随机地选择一个区间 𝑙, 𝑟 1 ≤𝑙≤𝑟≤𝑛 ,然后将这个区间内的数改成区间 内最大值(注意这样的区间共有 𝑛(𝑛+1) 2 个),最后每个数的期望大小是多少呢? 小Yuuka 非常热爱随机,所以她给出的输入序列也是随机的(随机方式见数 据规模和约定)。 对于每个数,输出它的期望乘 𝑛(𝑛+1) 2
𝑞 再对109 + 7取模的值。 【输入格式】 输入文件segment.in 第一行包含 2 个正整数 𝑛, 𝑞 ,表示序列里数的个数和操 作的个数。 接下来 1 行,包含 𝑛 个非负整数 𝑎1, 𝑎2, ⋯, 𝑎𝑛。 【输出格式】 输出文件为segment.out。 输出共 1 行,包含 𝑛 个整数,表示每个数的答案。 【样例输入1】 5 5 1 5 2 3 4 【样例输出1】 3152671 3796875 3692207 3623487 3515626 【样例输入输出2】 见选手目录下的segment/segment_ex1.in 与segment/segment_ex1.ans。 注意样例输入输出1 和2 不满足数据规模和约定中的生成方式。
NOI2016 浙江省队选拔赛第二试 线段树 【样例输入输出3】 见选手目录下的segment/segment_ex2.in 与segment/segment_ex2.ans。 【数据规模和约定】 对于所有的测试数据,保证序列中数的大小不超过 109 ,即 𝑎𝑖≤109 ,并 且每个数是 0 到 109 之间的随机整数。 各测试点满足以下约定: 测试点 𝑛 q 约定 1 ≤5 ≤5 无 2 ≤8 ≤400 3 ≤12 4 ≤30 5 ≤50 6 ≤100 7 8 ≤400 9 10
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
5 5
0 0 0 0 0