LOJ#2267. 「SDOI2017」龙与地下城【正态分布与中心极限定理】

题目描述：

link

题目分析：

正态分布函数： 当 $Y$ 较小时用 DP/FFT/求导快速幂，DP的复杂度是 $O(Y\ast XY)$ 的，考虑上一轮对下一轮的贡献是一个区间的形式，先打差分标记然后前缀和。求导做快速幂是 $O(X\ast XY)$ 的。 当 $Y$ 较大时用正态分布函数拟合求 $\left[\frac{A-n\mu }{\sqrt{n}\sigma },\frac{B-n\mu }{\sqrt{n}\sigma }\right]$ 的积分，用自适应辛普森，或者C++自带的$erf$函数 注意方差是${\sigma }^2$…

另外还有用去掉头尾优化FFT、以及模意义下的组合方法，详见这篇博客

Code：

#include<bits/stdc++.h> using namespace std; const double eps = 1e-8, Pi = acos(-1), K = 1/sqrt(2*Pi); int T,X,Y,A,B; double f(double x){return K*exp(-x*x/2);} double F(double L,double R){ return (R-L)*(f(L)+4*f((L+R)/2)+f(R))/6; } double Simpson(double L,double R,int dep){ double M=(L+R)/2,S=F(L,R),SL=F(L,M),SR=F(M,R); if(dep>3&&fabs(S-SL-SR)<eps) return S; return Simpson(L,M,dep+1)+Simpson(M,R,dep+1); } int main() { for(scanf("%d",&T);T--;){ scanf("%d%d",&X,&Y); double p = 1./X, mu = (X-1)*0.5, sig = (X*X-1)/12.0; if(Y<=800){ static double f[2][805*25]; int now=0,L=0,R=0; f[now][0]=1; for(int i=1;i<=Y;i++,now=!now){ for(int j=L;j<R+X;j++) f[!now][j]=0; while(L<=R&&f[now][L]<eps) ++L; while(L<=R&&f[now][R]<eps) --R; for(int j=L;j<=R;j++) f[!now][j]+=f[now][j]*p,f[!now][j+X]-=f[now][j]*p; R+=X-1; for(int j=L+1;j<=R;j++) f[!now][j]+=f[!now][j-1]; } for(int i=L+1;i<=R;i++) f[now][i]+=f[now][i-1]; for(int i=1;i<=10;i++) scanf("%d%d",&A,&B),printf("%.6f\n",f[now][min(R,B)]-(A<=L?0:f[now][min(R,A-1)])); } else for(int i=1;i<=10;i++){ scanf("%d%d",&A,&B); double l=(A-Y*mu)/(sqrt(Y*sig)),r=(B-Y*mu)/(sqrt(Y*sig)); printf("%.6f\n",Simpson(l,r,0)); } } }