P3600 随机数生成器

题意：随机生成一个长度为$n$，值域为$[1,x]$的数列，每次询问一个区间$[l,r]$的最小值，最终答案为所有询问的最大值，求答案的期望 ------------ 可以发现包含其他区间的区间对答案是没有影响的，首先把它们去掉 考虑枚举最大值$k$ 设所有区间都满足$min_{l,r}<=k$的概率为$P(k)$ 那么$k$对答案的贡献就是$k*[P(k)-P(k-1)]$ 设$f[i]$表示右端点$<=i$的区间都满足$min_{l,r}<=k$的概率 对于每一个$k$计算，$f[n]$即为$P(k)$ 有转移方程：$f[i]=\sum_{p=j}^if[p-1]*(k/x)*(1-k/x)^{i-p}$ 直接做是$n^3$的 发现可以拆项，计算$f[p-1]*(1-k/x)^{-p}$的前缀和即可 总复杂度$O(xn^2logn)$ ``` #include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define reg register using namespace std; typedef long long ll; const int N=2005,mod=666623333; struct node { int l,r; inline friend bool operator < (node a,node b) { return a.l==b.l?a.r<b.r:a.l<b.l; } }q[N],t[N]; int n,T,x,m,fi[N],nxt[N]; ll ans,invx,f[N],sum[N]; inline int read() { int x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=-1; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*w; } ll quickpow(ll n,ll k) { ll s=1; while (k) { if (k&1) s=s*n%mod; n=n*n%mod; k>>=1; } return s; } inline ll Sum(int l,int r){return (sum[r]-(l<1?0:sum[l-1])+mod)%mod;} inline ll calc(int k) { ll p1=1ll*k*invx%mod,p2=(1-p1+mod)%mod,p3=quickpow(p2,mod-2); memset(f,0,sizeof(f)); f[0]=1; memset(sum,0,sizeof(sum)); sum[0]=p3; for (reg int i=1;i<=n;i++) { for (reg int j=fi[i];j;j=nxt[j]) { if (i>q[j].l) f[i]=(f[i]+Sum(q[j].l-1,i-2)*p1%mod*quickpow(p2,i)%mod)%mod; f[i]=(f[i]+f[i-1]*p1%mod)%mod; } if (!fi[i]) f[i]=f[i-1]; sum[i]=(sum[i-1]+f[i]*quickpow(p3,i+1)%mod)%mod; } return f[n]; } int main() { n=read(),x=read(),T=read(); for (reg int i=1;i<=T;i++) t[i].l=read(),t[i].r=read(); sort(t+1,t+T+1); for (reg int i=1;i<=T;i++) { while (q[m].r>=t[i].r) --m; if (q[m].l<t[i].l) q[++m]=t[i]; } invx=quickpow(x,mod-2); ll pre=0; for (reg int i=1;i<=m;i++) nxt[i]=fi[q[i].r],fi[q[i].r]=i; for (reg int i=1;i<=x;i++) { ll now=calc(i); ans=(ans+1ll*i*((now-pre+mod)%mod)%mod)%mod; pre=now; } printf("%lld\n",ans); return 0; } ```