题解 P3600 【随机数生成器】

~~蒟蒻又来肝期望题啦。~~ 注意到这题$n,x$(由于本人习惯,下文均改为c)$,q$**同阶**。 非常罕见,一道期望题值域居然只有2000? 我们考虑**在值域上做手脚**。 ```cpp 不确定的东西越多,题目就越复杂。 复杂的数学题可以利用枚举降低思考复杂度。 ——某数学dalao 离散统计数学三兄弟:方案数,概率,期望 ——本蒟蒻 ``` 喜闻乐见得,这道题有膜,所以不用单行掉精度,方案数,概率,期望可以随意转化。 这道题求的是一番操作后,答案的期望,很明显,答案一定是$[1,c]$内的一个整数(也就是只有c种可能),所以答案是离散期望变量。 离散变量期望公式:$E(x)=\sum{P(?)*W(?)}$,其中$P$是概率,$W$是权值 或者你可以看看[某度百科](https://baike.baidu.com/item/%E6%95%B0%E5%AD%A6%E6%9C%9F%E6%9C%9B/5362790?fr=aladdin) 比如说如果你抛瓶盖,瓶盖正面朝上的概率0.4,反面0.6;抛到正面得2分,反面得1分。 那么抛一次,得分期望为 $0.4*2+0.6*1=1.4$。 总的来说,概率乘权值(分数)的和就得到期望 。 - **设**答案有$p[x]$的概率等于$x$ 。 那么答案的期望$\large{E(ans)=\sum\limits_{1<=i<=x}{i*p[i]}}$ 上面的的式子只有$p[]$是未知的,于是乎,我们**把期望问题转化为了概率问题**。 我们分别求出$p[1...c]$,再按照上面的式子算就可以了。 难点在$p$数组的求解上。 ------- 这道题有一系列$min/max$操作,都是**基于不等式**的,我们设的状态很乏力(**等于**$x$),考虑转化一下。 概率是可以容斥的(废话),比如这道题里,我们就可以定义一个基于不等式的状态$g[x]$。 - 设$g[x]$表示答案有$g[x]$的概率小于等于x。 这样的话,$\large{p[x]=g[x]-g[x-1]}$。 $g[x]$相对好求一些(~~真香~~)。 我们把数列**大于$x$的数都转化为1,小于等于$x$的都转化为0**,很明显,每个位置有$(c-x)/c$的可能为$1,x/c$的可能为$0$。 由于取$min$操作,每个区间会得到一个0或者1,如果一个区间内有0则必然得到0,**如果这个区间全是1,则得到1**。 后面再对所有的区间取$max$,**如果区间答案有任意一个1,则$ans>x$**(~~坏了一锅粥?~~)。 所以$ans<=x$的概率等于有**没有一个区间内全是1**的概率。 好像这个概率也不好求,**转化成方案数**吧(zz气息)。 众所周知:事件的概率=**事件发生方案数/总方案数**(这要建立在所有情况概率(权重)相等的情况下)。 ------- - **设**$r[x]$表示答案有$r[x]$种方案小于等于$x$。 我们把数列大于$x$的数都转化为1,小于等于$x$的都转化为0,很明显,每个位置有$(c-x)$种方案为1,$x$种方案为0。 明显看到,总方案数为$c^n$(每个数字都有c种取值,共n个) 所以$\large{g[x]=r[x]/(c^n)}$。 所以$ans<=x$的方案数等于没有一个区间内全是1的方案数。 我们要保证没有一个区间内全是1,即每个区间内至少有1个0。 现在问题来了:我们有几种方法填写01串,使得每个区间内至少有1个0? ```cpp 不会就多设几个数。 ——数学老师 forest·true·stop ``` - **设**$s[i]$为填了$i$个0,$(n-i)$个1,使得每个区间内至少有1个0的方案数。 一个1可以对应原值域中的$(c-x)$个数,一个0可以对应$x$个数。 则$\large{r[x]=\sum\limits_{0<=i<=n}{s[i]*(x^i*(c-i)^{(n-i)})}}$ ~~对于$s$,上$O(2^n)$枚举01串求。~~(应该有这个部分分才对) 对于$s$,不就是个填写01串的方案数问题吗?终于可以**dp求解了**! ------ - 设$f[i][j]$为在前i位置内填了j个0(必填第i位),且已经覆盖了左端点小于等于i的所有区间的方案数。 转移:很明显$f[i][j]$要从$f[?][j-1]$转移过来。 具体是那些"?"呢? 如果第i位一个0可以把左端点$posl$满足$?<pos<=i$的所有区间都干掉,这个?就是满足条件的。 把?从$i-1$(两个0不能放在一起)向前枚举就可以了。 判断不合法: 如果有左端点posl满足$?<pos<=i$的区间,右端点端点$posr<i$,则?不在这个区间内,不合法。 因为上一个0没有干掉这个区间,这个0也没有,所以这个区间可以~~苟且偷生~~,所以布星。 那么,求出来?之后 ,得到$\large{f[i][j]=\sum\limits_{?<=j<i}f[j][j-1]}$ 正确性满足了,接下来**上优化**。 ------- 我们来捋一捋程序过程与复杂度($n,c,q$同阶)。 先$dp$出$f$数组,一共状态$O(n^2)$,乘上转移$O(n)$。 O(n^3) $s[k]=\sum\limits_{1<=i<=n}{f[i][k]}\text{(i需要满足条件哦)}$ O(n^2) $r[x]=\sum\limits_{0<=i<=n}{s[i]*(i^k*(x-i)^{(n-k)})}$ O(n^2*logn)(快速幂) $g[x]=r[x]/(c^n)$ O(n) $p[x]=g[x]-g[x-1]$ O(n) $E(ans)=\sum\limits_{1<=i<=x}{i*p[i]}$ O(n) 空间无疑$O(n^2)$时间复杂度$O(n^3)$ **瓶颈在dp**,想办法加速转移。 回顾:如果有左端点posl满足$?<pos<=i$的区间,右端点端点$posr<i$,则?不在这个区间内,不合法。 很明显具有单调性嘛。 右端点做一个ST表,查处最小值,如果最小值$<i$,则$?$不合法(时间复杂度$O(1)$)。 二分+ST表就可以解决。 $?$的求解降到$O(logn)$剩下的加上前缀和就可以啦。 复杂度优化为$O(n^2logn)$,解决本题。 ~~代码有点恶心人~~ ------------ 其实不用二分优化,大力枚举r就可以了。 由于数据随机,r期望只用枚举$log(n)$次 上暴力版的代码吧,反正也AC了。 ~~正常版的太丑,不放了。~~ **Code: ** ```cpp #include<algorithm> #include<cstdio> #define mod 666623333 using namespace std; int n,c,q,h[2050]; long long f[2050][2050] ,s[2050],r[2050],g[2050],p[2050],ans; struct Line {int l,r;} b[2050]; long long pow(long long a,long long t) { long long ans=1,buff=a; while(t){ if (t&1) ans=(ans*buff)%mod; buff=(buff*buff)%mod; t>>=1; }return ans; } long long inv(long long num) {return pow(num,mod-2);} int main() { scanf("%d%d%d",&n,&c,&q); for (int i=1;i<=n;i++)h[i]=1<<30; for (int i=1;i<=q;i++){ scanf("%d%d",&b[i].l,&b[i].r); h[b[i].l]=min(h[b[i].l],b[i].r);//这句话是关键 }f[0][0]=1; for (int j=1;j<=n;j++){ for (int i=j;i<=n;i++){ int r=i-1; while(h[r]>=i&&r){ f[i][j]=(f[i][j]+f[r][j-1])%mod; r--;//一开始没有膜还得了80 }f[i][j]=(f[i][j]+f[r][j-1])%mod; //追求理论复杂度的话,可以把转移改成ST表+二分+前缀和优化(汗) } }for (int k=0;k<=n;k++) for (int i=n;i>-1;i--){ s[k]=(s[k]+f[i][k])%mod; if (h[i]<(1<<25))break; //如果这里放最后一个0满足不了最后一个区间,在前面放0都不合法。 } for (int x=1;x<=c;x++) for (int i=1;i<=n;i++) r[x]=(r[x]+s[i]*pow(x,i)%mod*pow(c-x,n-i))%mod; for (int x=1;x<=c;x++)g[x]=r[x]*inv(pow(c,n))%mod; for (int x=1;x<=c;x++)p[x]=(g[x]-g[x-1]+mod)%mod; for (int x=1;x<=c;x++)ans=(ans+x*p[x])%mod; //跟上面的式子一样的。 printf("%lld",ans); return 0; } ``` [$AC$记录](https://www.luogu.org/recordnew/show/15145944)