P3600 随机数生成器
Captain_Paul
2018-09-29 08:11:19
题意:随机生成一个长度为$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;
}
```