题解 P3779 【[SDOI2017]龙与地下城】

讲道理这道题会给人一种“还有这种操作”的感觉…… # 中心极限定理 ### 前置芝士：正态分布 什么是正态分布，所谓正态分布呢……就是一个随机变量X的一种分布形式，我们都知道一个随机变量的概率分布情况会有很多种，比如均匀分布，就是在一定值域内取每个地方的值的概率都是一样的，比如二项分布，只能是两种值(例如抛硬币) 然后正态分布就是各种概率分布情况的一种，它有什么用呢？正态分布有一个特点，就是它只需要一个期望$μ$和一个方差$σ^{2}$就可以描述，我们记做N($μ,σ^{2}$)，感性的理解的话，正态分布的特点是中间高，两边低，概率密度曲线为钟形 但是真正使正态分布重要的还是中心极限定理……这个后面讲 ### 前置芝士：概率密度函数 如果一个随机变量是离散的，我们似乎可以用一个表格，列出每个值出现的概率 但是如果我们要描述一个连续型随机变量呢？显然它取任何一个值的概率都是0啊……，但是显然值落在某一个区间的概率可以不是0啊 所以我们使用了一种被称为**概率密度函数**的东西来描述这个随机变量的分布情况 连续型随机变量x的概率密度函数f(x)需要满足这样一个条件，才可以是这个变量的概率密度函数 **f(x)在某一区间的积分，等于x落在这个区间的概率** 更粗暴的一点讲，f(x)在某一区间内和X轴所围成的图形面积等于X落在这个区间的概率 那么正态分布的概率密度函数是什么呢，设这个正态分布为N($μ,σ^{2}$)那么我们会发现它的概率密度函数为 ## $f(x)=\frac{1}{\sqrt{2πσ^{2}}}e^{-\frac{(x-μ)^{2}}{2σ^{2}}}$ 其中e的若干次方可以用cmath库中的exp()函数计算，所以我们一旦证明了一个变量服从正态分布，接下来的工作就是对着目标区间大力辛普森积分即可了 --------------- 中心极限定理的内容： 设有n个独立同分布的随机变量x，那么……满足…… 抱歉这个东西我看不懂…… 但是我们呢做这道题用的是中心极限定理一个较为亲民的一个**推论** 若有N个独立同分布的随机变量$x_{1}……x_{n}$期望为$μ$方差为$σ^{2}$ 那么设 # $Y_{n}=\frac{\sum^{n}_{i=1}x_{i}-nμ}{\sqrt{nσ^{2}}}$ 则当n足够大的时候~~(当满足我们的eps要求的时候)~~可以认为$Y_{n}$服从正态分布N(0,1) 所以我们发现一件事，出题人已经给了我们x的方差和期望了，我们此时运用一下高一数学的基本操作就可以发现，如果 ### $\sum^{n}_{i=1}xi∈[A,B]$ 那么有 ## $Y_{n}∈[\frac{A-nμ}{\sqrt{nσ^{2}}},\frac{B-nμ}{\sqrt{nσ^{2}}}]$ 此时我们发现一件事，这就是道中心极限定理的裸题…… 我们唯一要做的事就是转了A,B范围之后对着正态分布的概率密度函数大力辛普森积分，毕竟误差要求贼宽对吧……，但是再怎么说n=1之类的情况我们是不可以认为n足够大的，因此我们又要使用对数据分情况讨(骗)论(分)的技巧了 ## 小数据做法：快速傅里叶变换(FFT) 对于一些小的数据我们呢发现可以这样做 构造一个多项式，次数为0~x-1，我们呢希望这个构造出来的多项式满足这样一个条件：就是次数为a的项的系数就是**编号和为a的概率** 显然一开始每一项的系数都是$\frac{1}{x}$ 接下我们呢考虑转移，把这个式子平方一下，我们会发现新的多项式也满足刚才的性质，为什么呢？考虑我们在做乘法的时候做了什么，对于一个新的项，我们相当于枚举了这两次掷骰子的所有可能情况，相乘再相加，刚好和多项式乘法的工作原理相同，同理也有3次，4次，y次方的情况 或者你也可以认为是dp，转移方程是卷积的形式然后再去用fft优化 所以我们要做的事情就变得很简单了，构造这样一个多项式，然后计算它的y次方，最后再计算次数从A-B的和就OK了 ~~什么你不会fft?出门左转luogu膜板区，包教包会~~ ---------------- 之后就没啥难度了，如果你不会Simpson积分法的话这里可以简单的介绍下 ## 自适应Simpson积分法 大概就是我们要求一个函数的曲线下面积，然后我们怎么求呢？ 最简单的想法是切片法，定一个eps然后一路矩形切片切过去 另一种想法是梯形法，就是把刚才的矩形变成梯形，但是刚才的两种做法就是怕函数突变，所以我们需要采取一种更科学的方法-自适应Simpson积分法 我们粗暴的认为这个曲线是一个抛物线，我们这样就可以用抛物线的曲线下面积公式 ### $\frac{(r-l)(f(l)+4f(mid)+f(r))}{6}$ 来计算了，同时为了避免精度不够，我们再用l,mid和mid,r两部分的面积和来看一下差是否满足eps，如果精度不够就递归下去，最后我们就暴力的把这个函数的积分求了出来…… 下面上代码吧，写起来就是俩板子，挺好写的…… 上代码~ ```C #include<cstdio> #include<algorithm> #include<cmath> using namespace std; typedef double db; const db eps=1e-12;const int N=524300;const db pi=acos(-1);int T; const int Mlim=524288;const db K=1/sqrt(2*pi);int x;int y;int lim; struct cmp//虚数类 { db r;db v;cmp(db a=0,db b=0){r=a;v=b;} friend cmp operator +(cmp a,cmp b){return cmp(a.r+b.r,a.v+b.v);} friend cmp operator -(cmp a,cmp b){return cmp(a.r-b.r,a.v-b.v);} friend cmp operator *(cmp a,cmp b){return cmp(a.r*b.r-a.v*b.v,a.r*b.v+a.v*b.r);} void operator /=(db a){r/=a;v/=a;} }res[N];int r[N];int len; inline void clear(){for(int i=0;i<lim;i++){res[i]=cmp();r[i]=0;}} inline cmp po(cmp a,int p){cmp r(1,0);for(;p;p>>=1,a=a*a){if(p&1){r=r*a;}}return r;} inline void clacr(){for(int i=1;i<lim;i++){r[i]=r[i>>1]>>1|(i&1)<<len;}}//计算反转数组 inline void fft(cmp* tp,int n,int op)//fft板子 { for(int i=1;i<n;i++){if(i<r[i])swap(tp[i],tp[r[i]]);} for(int k=1;k<n;k<<=1) { for(int s=0;s<n;s+=2*k) { cmp now(1,0);cmp rt(cos(pi/k),op*sin(pi/k)); for(int i=s;i<s+k;i++,now=now*rt) {cmp ev=tp[i];cmp od=tp[i+k];tp[i]=ev+now*od;tp[i+k]=ev-now*od;} } }if(op==-1){for(int i=0;i<n;i++){tp[i]/=n;}} } inline db f(db x){return K*exp(x*x/-2.0);}//正态分布的概率密度函数 inline db psp(db l,db r){db mid=(l+r)/2.0;return (r-l)*(f(l)+4.0*f(mid)+f(r))/6.0;} inline db sp(db l,db r)//然后这是Simpson积分的板子 { db mid=(l+r)/2.0;db f1=psp(l,r);db f2=psp(l,mid)+psp(mid,r); db res=(-eps<f1-f2&&f1-f2<eps)?f1:sp(l,mid)+sp(mid,r);return res; } inline void solve() { scanf("%d%d",&x,&y);lim=x*y; if(lim<=Mlim)//判断一下fft跑的过去还是跑不过去 { for(len=0;(1<<len)<=lim;len++);lim=(1<<len);len--; clacr();for(int i=0;i<x;i++){res[i].r=1/(db)x;} fft(res,lim,1);//直接快速幂即可 for(int i=0;i<lim;i++){res[i]=po(res[i],y);} fft(res,lim,-1); for(int i=1;i<=10;i++) { int a;int b;scanf("%d%d",&a,&b);db ret=0; for(int j=a;j<=b;j++){ret+=res[j].r;} printf("%.6lf\n",ret); } } else//大数据套中心极限定理 { db mu=(db)(x-1)/2;db sigma=(db)(x*x-1)/12; for(int i=1;i<=10;i++)//大力转A,B范围之后计算积分即可 { db a;db b;scanf("%lf%lf",&a,&b); a=(a-y*mu)/sqrt(y*sigma);b=(b-y*mu)/sqrt(y*sigma); printf("%.6lf\n",sp(0,b)-sp(0,a)); }lim=0; } } int main() {scanf("%d",&T);for(int z=1;z<=T;z++){solve();clear();}return 0;//拜拜程序~} ```