首页 > 代码库 > bzoj4574 [Zjoi2016]线段树
bzoj4574 [Zjoi2016]线段树
Description
小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取模的值。
Input
第一行包含2个正整数n,q，表示序列里数的个数和操作的个数。接下来1行，包含n个非负整数a1,a2...an。N<=400,Q<=400
Output
输出共1行，包含n个整数，表示每个数的答案
Sample Input
5 5
1 5 2 3 4
1 5 2 3 4
Sample Output
3152671 3796875 3692207 3623487 3515626
正解：$dp$。
这道题还是太鬼了，我直接给一个博客吧：http://blog.csdn.net/qq_34637390/article/details/51290087
根本就不想写题解了。。
1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <queue>10 #include <stack>11 #include <map>12 #include <set>13 #define rhl (1000000007)14 #define N (410)15 #define il inline16 #define RG register17 #define ll long long18 19 using namespace std;20 21 int cal[N][N],a[N],s[N],rk[N],cnt[N],n,q;22 ll f[2][N][N],sum[N][N],ans;23 24 il int gi(){25 RG int x=0,q=1; RG char ch=getchar();26 while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();27 if (ch==‘-‘) q=-1,ch=getchar();28 while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar();29 return q*x;30 }31 32 il int cmp(const int &x,const int &y){ return a[x]<a[y]; }33 34 il void solve(RG int l,RG int r,RG int now){35 for (RG int i=l;i<=r;++i)36 for (RG int j=l;j<=r;++j) f[0][i][j]=f[1][i][j]=0;37 f[0][l][r]=1; RG ll res;38 for (RG int k=1,cur=1,p=0;k<=q;++k,p=cur,cur^=1){39 for (RG int j=l;j<=r;++j){40 res=0;41 for (RG int i=l;i<=j;++i)42 f[cur][i][j]=res,res+=f[p][i][j]*(ll)(i-1);43 }44 for (RG int i=l;i<=r;++i){45 res=0;46 for (RG int j=r;j>=i;--j){47 (f[cur][i][j]+=res+f[p][i][j]*(ll)cal[i][j])%=rhl;48 res+=f[p][i][j]*(ll)(n-j);49 }50 }51 }52 RG int cur=q&1;53 for (RG int i=l;i<=r;++i){54 res=0;55 for (RG int j=r;j>=i;--j)56 res+=f[cur][i][j],(sum[j][rk[now]]+=res)%=rhl;57 }58 return;59 }60 61 int main(){62 #ifndef ONLINE_JUDGE63 freopen("segment.in","r",stdin);64 freopen("segment.out","w",stdout);65 #endif66 n=gi(),q=gi();67 for (RG int i=1;i<=n;++i) a[i]=gi(),s[i]=i,cnt[i]=i*(i+1)>>1;68 sort(s+1,s+n+1,cmp); for (RG int i=1;i<=n;++i) rk[s[i]]=i;69 for (RG int i=1;i<=n;++i)70 for (RG int j=i;j<=n;++j) cal[i][j]=cnt[i-1]+cnt[n-j]+cnt[j-i+1];71 for (RG int i=1,l,r;i<=n;++i){72 l=r=i; while (l && a[l]<=a[i]) --l;73 while (r<=n && a[r]<=a[i]) ++r; solve(l+1,r-1,i);74 }75 for (RG int i=1;i<=n;++i){76 ans=0;77 for (RG int j=1;j<=n;++j){78 if (!sum[i][j]) continue;79 for (RG int k=1;k<j;++k) (sum[i][j]-=sum[i][k])%=rhl;80 (ans+=sum[i][j]*(ll)a[s[j]])%=rhl;81 }82 (ans+=rhl)%=rhl;83 if (i!=n) printf("%lld ",ans); else printf("%lld",ans);84 }85 return 0;86 }
bzoj4574 [Zjoi2016]线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。