题面 https://www.luogu.org/problemnew/show/P4986
我居然不会写多项式卷积了, 把 $a[i]=a[i]*b[i]$ 写成了 $a[i].x=a[i].x*b[i].x$ 还调了好长时间, 有毒
把式子写成 $C^2(x)-A^2(x)-B^2(x)=0$ 的形式, 然后牛顿迭代即可
- #include<cmath>
- #include<cstdio>
- #include<cctype>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- const int N=800005;
- const double pai=acos(-1),inf=1e9,eps=1e-6;
- struct cpx
- {
- double x,y;
- }a[N],b[N],c[N];
- cpx operator + (cpx a,cpx b)
- {
- return (cpx){a.x+b.x,a.y+b.y};
- }
- cpx operator - (cpx a,cpx b)
- {
- return (cpx){a.x-b.x,a.y-b.y};
- }
- cpx operator * (cpx a,cpx b)
- {
- double x1=a.x,y1=a.y,x2=b.x,y2=b.y;
- return (cpx){x1*x2-y1*y2,x1*y2+y1*x2};
- }
- int la,lb,lc,n,m,nm,rev[N];
- double ll,rr,Sin[32],Cos[32],f[N],d[N];
- void Read(double &x)
- {
- int ret=0; x=0;
- char ch=getchar();
- while(!isdigit(ch))
- ch=getchar();
- while(isdigit(ch))
- ret=(ret<<1)+(ret<<3)+(ch^48),ch=getchar();
- x=ret; return ;
- }
- void Prework()
- {
- m=2*(max(la,max(lb,lc))+1),n=1; while(n<=m) n<<=1;
- for(int i=0;i<=n;i++)
- rev[i]=(rev[i>>1]>>1)+(i&1)*(n>>1);
- for(int i=1;i<=24;i++)
- Sin[i]=sin(2*pai/(1<<i)),Cos[i]=cos(2*pai/(1<<i));
- }
- void Trans(cpx *cop,int len,int typ)
- {
- register int i,j,k;
- for(i=0;i<=len;i++)
- if(rev[i]>i) swap(cop[rev[i]],cop[i]);
- for(i=2;i<=len;i<<=1)
- {
- int lth=i>>1,lgg=log2(i);
- cpx omg=(cpx){Cos[lgg],typ*Sin[lgg]};
- for(j=0;j<len;j+=i)
- {
- cpx ori={1,0};
- for(k=j;k<j+lth;k++,ori=ori*omg)
- {
- cpx tmp=ori*cop[k+lth];
- cop[k+lth]=cop[k]-tmp,cop[k]=cop[k]+tmp;
- }
- }
- }
- if(typ==-1)
- for(int i=0;i<=len;i++) cop[i].x/=len;
- }
- void Square(cpx *cop,int len)
- {
- register int i;
- Trans(cop,len,1);
- for(i=0;i<=len;i++)
- cop[i]=cop[i]*cop[i];
- Trans(cop,len,-1);
- }
- double Ask(double *f,double x,int len)
- {
- double ret=0,var=1;
- for(int i=0;i<=len;i++)
- ret+=f[i]*var,var*=x;
- return ret;
- }
- double Iterate(double x)
- {
- for(int i=1;i<=30;i++)
- {
- double y=Ask(f,x,n);
- if(fabs(y)<=eps) return x;
- x-=y/Ask(d,x,nm),x=max(x,ll),x=min(x,rr);
- }
- return inf;
- }
- int main()
- {
- register int i;
- scanf("%d%d%d%lf%lf",&la,&lb,&lc,&ll,&rr);
- for(i=0;i<=la;i++) Read(a[i].x);
- for(i=0;i<=lb;i++) Read(b[i].x);
- for(i=0;i<=lc;i++) Read(c[i].x);
- Prework(),Square(a,n),Square(b,n),Square(c,n);
- for(i=0;i<=n;i++) c[i]=c[i]-a[i]-b[i]; nm=n-1;
- for(i=0;i<=n;i++) f[i]=c[i].x,d[i]=(i+1)*c[i+1].x;
- double ans=Iterate((ll+rr)/2);
- ans>=inf?printf("Inconsistent!"):printf("%.8f",ans);
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2930819.html