【xsy1131】tortue FFT

题目大意：

一次游戏要按N个按键。每个按键阿米巴有P[i]的概率按错。对于一串x个连续按对的按键，阿米巴可以得分

$f(x)=tan(\dfrac{x}{N})\times e^{arcsin(0.8\times \frac{x}{N})}\times N$

在阿米巴疯狂的玩这款游戏之前，小强想知道，阿米巴的期望得分是多少。

数据范围：$n≤10^5$

貌似题解是泰勒展开，然而我自己想的做法是分治FFT，最后写了个没有分治的FFT。

我们记$S_i$表示连续按下至少$i$个按键的期望次数。

那么答案显然为$\sum_{i=1}^{n}S_i-2S_{i+1}+S_{i+2}$

考虑如何求$S$，不难发现$S_i=\sum_{j=1}^{n-i+1}\prod_{k=0}^{i-1}(1-P[j+k])$

直接求显然是$O(n^3)$的，通过前缀积优化一发可以做到$O(n^2)$

我们构造序列$F$和序列$G$，令$F_i=\prod_{j=1}^{i}(1-P[j])$，$G_i=\dfrac{1}{\prod_{j=1}^{i-1}(1-P[n-j])}$。

不难发现，$S_i=\sum_{j=1}^{i}F_{j}G_{i-j+1}$

我们用FFT加速一波就可以求了

时间复杂度：$O(n\log\ n)$。

PS：此题卡精度，不要尝试使用两次FFT做卷积，要用三次FFT！！！

 #include<bits/stdc++.h>

 #define M (1<<18)

 #define PI acos(-1)

 using namespace std;

 struct cp{

     double i,r;

     cp(double R=,double I=){i=I; r=R;}

     friend cp operator +(cp a,cp b){return cp(a.r+b.r,a.i+b.i);}

     friend cp operator -(cp a,cp b){return cp(a.r-b.r,a.i-b.i);}

     friend cp operator *(cp a,cp b){return cp(a.r*b.r-a.i*b.i,a.r*b.i+a.i*b.r);}

     friend cp operator /(cp a,double b){return cp(a.r/b,a.i/b);}

 }a[M],b[M];

 void change(cp a[],int len){

     for(int i=,j=;i<len-;i++){

         if(i<j) swap(a[i],a[j]);

         int k=len>>;

         while(j>=k) j-=k,k>>=;

         j+=k;

     }

 }

 void FFT(cp a[],int len,int on){

     change(a,len);

     for(int h=;h<=len;h<<=){

         cp wn=cp(cos(*PI/h),sin(*PI/h*on));

         for(int j=;j<len;j+=h){

             cp w=cp(,);

             for(int k=j;k<j+(h>>);k++){

                 cp u=a[k],t=w*a[k+(h>>)];

                 a[k]=u+t; a[k+(h>>)]=u-t;

                 w=w*wn;

             }

         }

     }

     if(on==-){

         for(int i=;i<len;i++)

         a[i]=a[i]/len;

     }

 }

 double p[M]={},s[M]={},ans=;int n;

 double f(double x){return tan(x/n)*exp(asin(0.8*x/n))*n;}

 int main(){

     scanf("%d",&n);

     for(int i=;i<n;i++) scanf("%lf",p+i),p[i]=-p[i];

     a[].r=; for(int i=;i<n-;i++) a[i+].r=a[i].r/p[i];

     b[n-].r=p[]; for(int i=n-;~i;i--) b[i].r=b[i+].r*p[n-i-];

     int m=; for(;m<n*;m<<=);

     FFT(a,m,); FFT(b,m,);

     for(int i=;i<m;i++) a[i]=a[i]*b[i];

     FFT(a,m,-);

     for(int i=;i<=n;i++) s[i]=a[n-i].r;

     for(int i=;i<=n;i++) ans+=(s[i]-*s[i+]+s[i+])*f(i);

     printf("%.10lf\n",ans);

 }

巴特西

【xsy1131】tortue FFT

最新文章

热门文章