逃离【题解】

周道_Althen · 2018-10-14 17:23:12 · 题解

大家好我是出题人 Althen·Way·Satan（超小声）。

热烈祝贺第一个切掉这个题的人：@南山桥一霸；

还有感谢一直到最后都在肝我的题的大佬，葱花都要哭出来了：@zhaimingshuzms。（Orz，都已经拿到70%了）

• 前排鸣谢：

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cstdio>
#include<string>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
using　namespace　std;
const　double　eps=1e-10;
const　double　pi=acos(-1.0);
inline　int　read(){
　　int　x=0,f=1;char　ch;ch=getchar();
　　while(ch<'0'||ch>'9'){if(ch=='-')　f=0;ch=getchar();}
　　while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch&15);ch=getchar();}
　　if(f)return　x;else　return　-x;
}
double　fabs(double　c){if(c<0.0)return　-c;return　c;}
const　int　N=3e5+10;
//FFT模板————————————————————————————————————　
struct　cpx{
　　double　r,i;
　　inline　cpx　operator　*(const　cpx&x)const{return　(cpx){r*x.r-i*x.i,r*x.i+i*x.r};}
　　inline　cpx　operator　+(const　cpx&x)const{return　(cpx){r+x.r,i+x.i};}
　　inline　cpx　operator　-(const　cpx&x)const{return　(cpx){r-x.r,i-x.i};}
}cpxa[N],cpxb[N];
int　r[N];
void　FFT(cpx*a,int　f,int　la){
　　int　n=la;
　　for(register　int　i=0;i<n;++i)if(i<r[i])swap(a[i],a[r[i]]);
　　for(register　int　i=1;i<n;i<<=1){
　　　　cpx　wn=(cpx){cos(pi/i),f*sin(pi/i)};
　　　　for(register　int　j=0;j<n;j+=(i<<1)){
　　　　　　cpx　w=(cpx){1,0};
　　　　　　for(register　int　k=0;k<i;++k,w=w*wn){
　　　　　　　　cpx　x=a[j+k],y=w*a[j+k+i];
　　　　　　　　a[j+k]=x+y;a[j+k+i]=x-y;
　　　　　　}
　　　　}
　　}
　　if(f==-1)
　　for(register　int　i=0;i<n;i++)a[i].r/=n;
}
int　merge_fft(cpx　*a,cpx　*b,int　la,int　lb){
　　int　n=la,m=lb;
　　int　L=0;for(m+=n,n=1;n<=m;n<<=1)L++;
　　for(register　int　i=0;i<n;i++)
　　r[i]=(r[i>>1]>>1)|((i&1)<<(L-1));
　　FFT(a,1,n);FFT(b,1,n);
　　for(register　int　i=0;i<=n;i++)a[i]=a[i]*b[i];
　　FFT(a,-1,n);
　　return　m;
}
//————————————————————————————————————————　
double　L,R;
int　La,Lb,Lc,Lc1,a[N],b[N],c[N],c1[N];
//函数平方
void　get_square(int　*a,int　&L){　
　　memset(cpxa,0,sizeof(cpxa));
　　memset(cpxb,0,sizeof(cpxb));
　　for(register　int　i=0;i<=L;i++)
　　cpxb[i].r=cpxa[i].r=(double)a[i];
　　L=merge_fft(cpxa,cpxb,L,L);
　　for(register　int　i=0;i<=L;i++)a[i]=(int)(cpxa[i].r+0.1);
}
//求C(x)的值
double　get_val_C(double　x){
　　double　X=1,Ret=0;
　　for(int　i=0;i<=Lc;i++){Ret=Ret+c[i]*X;X=X*x;}
　　return　Ret;
}
//求C1(x)的值
double　get_val_C1(double　x){
　　double　X=1,Ret=0;
　　for(int　i=0;i<=Lc1;i++){Ret=Ret+c1[i]*X;X=X*x;}
　　return　Ret;
}
//牛顿迭代　———————————————————————————————————　
int　tim=30;//设定迭代次数tim　
double　Newton_Iteration(double　x){//输入F(x)的初值F(0)，既迭代系数。　
　　double　c;
　　while(1){
　　　　c=get_val_C(x);//求出f(F(x))的值　
        　　tim--;
　　　　if(fabs(c)<eps)break;//若是F(x)在该精度下已经合法，便弹出。　
　　　　x=x-c/get_val_C1(x);//求出F(x)-f(F(x))/f'(F(x))的值，赋给F(x+1)　
　　　　x=max(x,L);x=min(x,R);//防止越界　
　　　　if(!tim)return　0;//若是在迭代次数tim内不合法，便弹出无解。　
　　}
　　return　x;
}
int　main()
{
　　La=read();Lb=read();Lc=read();scanf("%lf%lf",&L,&R);
　　for(int　i=0;i<=La;i++)a[i]=read();
　　for(int　i=0;i<=Lb;i++)b[i]=read();
　　for(int　i=0;i<=Lc;i++)c[i]=read();
　　for(register　int　i=0;i<=La;i++)
　　cpxb[i].r=cpxa[i].r=(double)a[i];
　　
　　//把c^2(x)-a^2(x)-b^2(x)存进c　
　　get_square(a,La);
　　get_square(b,Lb);
　　get_square(c,Lc);
　　Lc=max(Lc,max(La,Lb));
　　for(register　int　i=0;i<=Lc;i++)
　　c[i]=c[i]-b[i]-a[i];
　　
　　//求c1(x)为c(x)的一阶导数　
　　Lc1=Lc-1;
　　for(int　i=1;i<=Lc;i++)
　　c1[i-1]=c[i]*i;
　　
　　double　ans=Newton_Iteration((L+R)/2.0);
　　if(tim)　printf("%.8lf\n",ans);
　　else　printf("Inconsistent!\n");
　　return　0;
}

\ \ \ \ \ \ 这道题就这样解完了。