题解 P3779 【[SDOI2017]龙与地下城】
shadowice1984
2018-03-15 16:33:08
讲道理这道题会给人一种“还有这种操作”的感觉……
# 中心极限定理
### 前置芝士:正态分布
什么是正态分布,所谓正态分布呢……就是一个随机变量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;//拜拜程序~}
```