P3600 随机数生成器

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;
}