隐藏
「ZJOI2016」线段树 - 概率+动态规划 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「ZJOI2016」线段树 - 概率+动态规划

题目大意

    小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;
}
姥爷们赏瓶冰阔落吧~