自动搬运

查看原文

来自洛谷，原作者为

	shadowice1984 これが勘違いでも、これが勘違いでも

搬运于2025-08-24 21:52:36，当前版本为作者最后更新于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，如果精度不够就递归下去，最后我们就暴力的把这个函数的积分求了出来……

下面上代码吧，写起来就是俩板子，挺好写的……

上代码~

#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;//拜拜程序~}