首页 > 代码库 > 【洛谷P3600】 随机数生成器
【洛谷P3600】 随机数生成器
https://www.luogu.org/problem/show?pid=3600#sub (题目链接)
题意
一个$n$个数的序列，里面每个数值域为$[1,X]$。给$q$个区间，每个区间的权值为这段区间里面的最小的数，然后算出了一个$ans=min(q_i)$，问$ans$的期望大小。
Solution
md，太久没写题了，菜的抠脚了已经。
官方题解写的挺好的：https://www.luogu.org/discuss/show?postid=7867
细节
删除包含区间。
代码
// luogu3600#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=2010,MOD=666623333;int n,m,X,Q;LL f[maxn],s[maxn],inv[maxn],ans;struct data {int l,r;}q[maxn],t[maxn];bool cmp(data a,data b) { return a.l==b.l ? a.r<b.r : a.l<b.l;}LL power(LL a,LL b) { LL res=1; while (b) { if (b&1) (res*=a)%=MOD; b>>=1;(a*=a)%=MOD; } return res;}int main() { scanf("%d%d%de",&n,&X,&Q); for (int i=1;i<=Q;i++) scanf("%d%d",&q[i].l,&q[i].r); sort(q+1,q+1+Q,cmp); for (int i=1;i<=Q;i++) { while (q[m].r>=q[i].r && m) m--; if (q[i].l>q[m].l && q[i].r>q[m].r) q[++m]=q[i]; } for (int l=1,r=0,i=1;i<=n;i++) { while (r<m && q[r+1].l<=i && i<=q[r+1].r) r++; while (l<=m && q[l].r<i) l++; t[i]=(data){l,r}; } f[0]=inv[0]=1; for (int x=1;x<=X;x++) { LL T=power(X,MOD-2)*(x-1)%MOD,P=(1-T+MOD)%MOD,B=power(P,MOD-2),K=1,S=1,sum=0; for (int i=1;i<=n;i++) inv[i]=inv[i-1]*B%MOD; for (int p=0,i=1;i<=n;i++,(K*=P)%=MOD) { for (;p<i && t[p].r<t[i].l-1;p++) (S+=MOD-inv[p]*f[p]%MOD)%=MOD; f[i]=S*K%MOD*T%MOD; (S+=f[i]*inv[i]%MOD)%=MOD; } K=1; for (int i=n;i>=1;i--,(K*=P)%=MOD) if (t[i].r==m) (sum+=f[i]*K%MOD)%=MOD; (ans+=(1-sum+MOD))%=MOD; } printf("%lld",ans); return 0;}
【洛谷P3600】 随机数生成器
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。