线段树
提交数: 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