题目大意
小Yuuka遇到了一个题目：有一个序列$a_1,a_2,\ldots,a_n$，$q$次操作，每次把一个区间内的数改成区间内的最大值，问最后每个数是多少。小Yuuka很快地就使用了线段树解决了这个问题。
于是充满智慧的小Yuuka想，如果操作是随机的，即在这$q$次操作中每次等概率随机地选择一个区间$[l,r]$$(1\le l\le r\le n)$，然后将这个区间内的数改成区间内最大值（注意这样的区间共有$(n(n+1))/2$个），最后每个数的期望大小是多少呢？
小Yuuka非常热爱随机，所以她给出的输入序列也是随机的（随机方式见数据规模和约定）。对于每个数，输出它的期望乘$((n(n+1))/2)^q$再对$10^9+7$取模的值。
题目分析
不难想到使用区间动规的方式进行计算。
为了使得转移更科学，我们需要规定区间与其两边的数的大小关系。
设$f(x,i,l,k)$表示经过前$i$轮操作，$[l,r]$的所有数$\le x$，且$l-1$和$r+1$都$\gt x$的方案数。
转移很简单，从某个更大的区间转移而来，枚举一下那个区间边界在哪儿：
其中$g(l,r)$表示选择的区间对$(l,r)$不造成影响的方案数，显然为：
利用前缀和优化一下上述转移，可以得到基于随机的$O(n^4)$算法。
考虑统计答案。
设$h(x,i)$表示最终位置$i$的数$\le x$的方案数，$h(x,i)=\sum\limits_{l=1}^i\sum\limits_{r=i}^nf(x,q,l,r)$。
故$ans(i)=\sum_xx\times(h(x,i)-h(x-1,i))$。
现在考虑优化上述动规。
将答案式展开：
故设置$dp(i,l,r)=\sum_x -f(x,q,l,r)$，然后照样转移即可。
注意初始化。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {
if(x=='-')bj=-1;
x=getchar();
}
while(isdigit(x)) {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=405,p=1e9+7;
int n,q,a[maxn],f[2][maxn][maxn],sum1[2][maxn][maxn],sum2[2][maxn][maxn],g[maxn][maxn];
int main() {
n=Get_Int();
q=Get_Int();
a[0]=a[n+1]=INT_MAX/2;
for(int i=1; i<=n; i++)a[i]=Get_Int();
for(int i=1; i<=n; i++) {
int Max=0;
for(int j=i; j<=n; j++) {
g[i][j]=(i*(i-1)>>1)+((n-j+1)*(n-j)>>1)+((j-i+2)*(j-i+1)>>1);
Max=max(Max,a[j]);
if(i==1&&j==n)f[0][i][j]=Max;
else if(a[i-1]>Max&&a[j+1]>Max)f[0][i][j]=(Max-min(a[i-1],a[j+1])+p)%p;
}
}
int now=0,pre=1;
for(int i=1; i<=q; i++) {
swap(now,pre);
for(int j=1; j<=n; j++)
for(int k=n; k>=j; k--)
sum2[pre][j][k]=(sum2[pre][j][k+1]+1ll*f[pre][j][k]*(n-k))%p;
for(int j=1; j<=n; j++)
for(int k=j; k<=n; k++) {
sum1[pre][j][k]=(sum1[pre][j-1][k]+1ll*f[pre][j][k]*(j-1))%p;
f[now][j][k]=(1ll*f[pre][j][k]*g[j][k]+sum1[pre][j-1][k]+sum2[pre][j][k+1])%p;
}
}
for(int i=1; i<=n; i++) {
int sum=0;
for(int j=1; j<=i; j++)
for(int k=i; k<=n; k++)sum=(sum+f[q&1][j][k])%p;
printf("%d",sum);
if(i!=n)putchar(' ');
}
return 0;
}
|
