P3600 随机数生成器
斯德哥尔摩
2018-10-04 23:21:03
[P3600 随机数生成器](https://www.luogu.org/problemnew/show/P3600)
### 首先是乱搞：
我们发现包含其他区间的区间对答案是没有影响的。
所以先把它们去掉。
考虑枚举最大值$k$，设所有区间都满足$\min_{l,r}<=k$的概率为$P(k)$
那么$k$对答案的贡献就是$k\times[P(k)-P(k-1)]$。
设$dp[i]$表示$\text{右端点}<=i$的区间都满足$min_{l,r}<=k$的概率。
对于每一个$k$进行计算，则$dp[n]$即为$P(k)$。
转移方程长这个样：$$dp[i]=\sum_{p=j}^idp[p-1]\times\frac{k}{x}\times(1-\frac{k}{x})^{i-p}$$
直接做是$O(n^3)$的，很显然$TLE$对吧。。。
然后我们发现发现可以拆项。
即只要计算$dp[p-1]\times(1-\frac{k}{x})^{-p}$的前缀和即可。
总复杂度$O(xn^2\log_2n)$。
------------
### 下面是官方题解：
~~前方高能！前方高能！！前方高能！！！~~
首先如果两个询问区间为$[l1,r1]$和$[l2,r2]$，$[l2,r2]$被$[l1,r1]$完全包含。
即：$l1 \leq l2 \leq r2 \leq r1$。
那么$[l1,r1]$就废了，因为它的询问结果肯定较小。
排序预处理一下就可以去掉所有这些没用的区间了。
有用的区间左端点两两不同，而且按左端点排序，右端点就会严格递增。
我们考虑有限的期望公式，对于一个随机整数变量$x \geq 0$，它的期望为：$$E(x)=\sum_{\text{整数}s\geq 1}P(x \geq s)$$
我们考虑如何暴力地求出$P(x \geq s)$。
直接算不是很方便，我们考虑计算$1-P(x \leq s-1)$。
既然测试结果是这些询问得到的结果的最大值，那么只要保证每个询问结果都$\leq s-1$就好了，即每个询问区间内都至少有一个数$\leq s-1$。
考虑搞一个$dp$，我们用$dp[i][j]$表示考虑$a_1,a_2,a_3,...,a_i$的时候能满足询问$[1,j]$的概率，前面排序后这个东西可以简单地$dp$出来。
这样就能获得50分了！（感觉如果按这个思路也是能做满分的，不过出题人比较菜没有想出来）
考虑我们换一种思路来做，对于每个元素考虑它能满足哪些询问。
我们可以发现满足的询问一定是一个连续区间，而且依次考虑每个元素得到的每个询问区间也是满足左端点右端点都不降的。
这样我们就把问题转化成了：
有若干个区间，这些区间左右端点都不降，要覆盖整段，每个区间选的概率为$p=\frac{s-1}{x}$，问覆盖全段的概率。
考虑用$dp[i]$]表示考虑前$i$个区间，选择第$i$个区间，覆盖$[1,i]$区间右端点的概率，它可以用前面任意一个与第$i$个区间有交集的区间来转移。
容易得到转移方程：$$dp[i]=p\times(\sum_{r[j] \geq l[i]-1}dp[j]\times (1-p)^{i-j-1}+[l[i]=1](1-p)^{i-1})$$。
答案就是：$$\sum_{r[i]=n}dp[i]\times(1-p)^{n-i}$$
考虑把$dp$的转移方程写的美观一点：$$dp[i]=p\times(\sum_{r[j] \geq l[i]-1}dp[j]\times (1-p)^{-j}\times(1-p)^{i-1}+[l[i]=1](1-p)^{i-1})$$
这样我们大概可以用一个树状数组来维护$f[j]\times (1-p)^{-j}$？
如果你真的这样写了$70$分，那么恭(ha)喜(ha)你(ha)了(ha)。
既然$l[i],r[i]$都不降，只要$two-pointer$一下就是线性的了。
这样就过了。。。
其实$x \leq 10^7$也是能做的，不过没(lan)什(de)么(xie)意(biao)思(cheng)就不出了。
------------
然后我比较懒，就没有写正解了。。。
附上乱搞代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 2010
#define MOD 666623333LL
using namespace std;
int n,m,q,num=0;
int front[MAXN],after[MAXN];
long long inv,dp[MAXN],sum[MAXN];
struct Question{
int l,r;
friend bool operator <(const Question &p,const Question &q){
if(p.l==q.l)return p.r<q.r;
return p.l<q.l;
}
}a[MAXN],que[MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
long long mexp(long long a,long long b,long long c){
long long s=1;
while(b){
if(b&1)s=s*a%c;
a=a*a%c;
b>>=1;
}
return s;
}
inline long long get_sum(int l,int r){return (sum[r]-(l<1?0:sum[l-1])+MOD)%MOD;}
long long solve(int k){
long long x=1LL*k*inv%MOD,y=(1-x+MOD)%MOD,z=mexp(y,MOD-2,MOD);
memset(dp,0,sizeof(dp));
memset(sum,0,sizeof(sum));
dp[0]=1;
sum[0]=z;
for(int i=1;i<=n;i++){
for(int j=front[i];j;j=after[j]){
if(i>que[j].l)dp[i]=(dp[i]+get_sum(que[j].l-1,i-2)*x%MOD*mexp(y,i,MOD)%MOD)%MOD;
dp[i]=(dp[i]+dp[i-1]*x%MOD)%MOD;
}
if(!front[i])dp[i]=dp[i-1];
sum[i]=(sum[i-1]+dp[i]*mexp(z,i+1,MOD)%MOD)%MOD;
}
return dp[n];
}
void work(){
long long ans=0,last=0;
for(int i=1;i<=m;i++){
long long now=solve(i);
ans=(ans+1LL*i*((now-last+MOD)%MOD)%MOD)%MOD;
last=now;
}
printf("%lld\n",ans);
}
void init(){
n=read();m=read();q=read();
inv=mexp(m,MOD-2,MOD);
for(int i=1;i<=q;i++){a[i].l=read();a[i].r=read();}
sort(a+1,a+q+1);
for(int i=1;i<=q;i++){
while(que[num].r>=a[i].r)num--;
if(que[num].l<a[i].l)que[++num]=a[i];
}
for(int i=1;i<=num;i++){
after[i]=front[que[i].r];
front[que[i].r]=i;
}
}
int main(){
init();
work();
return 0;
}
```