题目大意
小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; }
|