线段树
提交数: 7, 通过率: 28.57%, 平均分: 41.43
题目描述:
小Yuuka遇到了一个题目:有一个序列a_1,a_2,?,a_n,q次操作,每次把一个区间内的数改成区间内的最大值,问最后每个数是多少。小Yuuka很快地就使用了线段树解决了这个问题。于是充满智慧的小Yuuka想,如果操作是随机的,即在这q次操作中每次等概率随机地选择一个区间[l,r](1≤l≤r≤n),然后将这个区间内的数改成区间内最大值(注意这样的区间共有(n(n+1))/2个),最后每个数的期望大小是多少呢?小Yuuka非常热爱随机,所以她给出的输入序列也是随机的(随机方式见数据规模和约定)。对于每个数,输出它的期望乘((n(n+1))/2)^q再对10^9+7取模的值。
输入格式:
第一行包含2个正整数n,q,表示序列里数的个数和操作的个数。接下来1行,包含n个非负整数a1,a2...an。N<=400,Q<=400
输出格式:
输出共1行,包含n个整数,表示每个数的答案
样例输入:
5 5 1 5 2 3 4
样例输出:
3152671 3796875 3692207 3623487 3515626
提示:
【样例输入输出2】
见选手目录下的segment/segment_ex1.in与segment/segment_ex1.ans。
注意样例输入输出1和2不满足数据规模和约定中的生成方式。
【样例输入输出3】
见选手目录下的segment/segment_ex2.in与segment/segment_ex2.ans。
【数据规模和约定】
对于所有的测试数据,保证序列中数的大小不超过 ,即 ,并且每个数是 到 之间的随机整数。
各测试点满足以下约定:
测试点 |
q |
约定 |
|
1 |
无 |
||
2 |
|||
3 |
|||
4 |
|||
5 |
|||
6 |
|||
7 |
|||
8 |
|||
9 |
|||
10 |
空间限制: 256MB
来源: 浙江省选2016day2t2