Luogu4546 [THUWC2017]在美妙的数学王国中畅游

想到不联通显然 (LCT),那么变成抄式子,给了泰勒展开那么维护若干项即可:

考虑 (sin(x)) 的泰勒展开:

[f(x)=sin(x),f'(x)=cos(x),f''(x)=-sin(x),f'''(x)=cos(x),f''''(x)=sin(x) ]

那么复合函数求导数得到:

[(f(g(x)))'=f'(g(x)) imes g'(x) ]

所以套上去就得到了 (sin(ax+b)) 的泰勒展开的式子,也就是乘上 (a) 的若干次方

考虑 (e^{ax+b}) 的展开

(f(x)=e^x,g(x)=a(x)+b),还是能得到 ((f(g(x)))')

[(f(g(x)))'=f'(g(x)) imes g'(x)=af(g(x)) ]

多求导就是多乘 (a)

那么套上 (Tyler) 展开的式子,维护每次的系数和,剩下的都是「模板」(LCT)

所以这题的收获是 (Tyler) 展开科技:(f(x)=sum frac{f'(x) imes x^i}{i!})

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define int long long 
namespace yspm{
    inline int read(){
        int res=0,f=1; char k;
        while(!isdigit(k=getchar())) if(k=='-') f=-1;
        while(isdigit(k)) res=res*10+k-'0',k=getchar();
        return res*f;
    }const int N=1e5+10;
    int fa[N],tp[N],ls[N],rs[N],n,Q; bool tag[N];
    double a[N],b[N],sum[N][20];
    inline bool isroot(int x){return ls[fa[x]]!=x&&rs[fa[x]]!=x;}
    inline void push_up(int x){
        for(reg int i=0;i<=16;++i)sum[x][i]=sum[ls[x]][i]+sum[rs[x]][i];
        if(tp[x]==1){
            double s=sin(b[x]),c=cos(b[x]),v=1;
            for(reg int i=0;i<=15;i+=4) sum[x][i]+=s*v,v*=a[x],sum[x][i+1]+=c*v,v*=a[x],sum[x][i+2]-=s*v,v*=a[x],sum[x][i+3]-=c*v,v*=a[x];
        }else if(tp[x]==2){
            double p=exp(b[x]),v=1; for(reg int i=0;i<=15;++i) sum[x][i]+=v*p,v*=a[x];
        }else sum[x][0]+=b[x],sum[x][1]+=a[x];  return ;
    }
    inline double query(double x,int rt){
        double ans=0,fac=1,p=1; for(reg int i=0;i<16;++i) ans+=p*sum[rt][i]/fac,fac*=i+1,p*=x;
        return ans;
    }
    inline void pushr(int x){swap(ls[x],rs[x]); tag[x]^=1; return ;}
    inline void push_down(int x){if(!tag[x]) return ; if(ls[x]) pushr(ls[x]); if(rs[x]) pushr(rs[x]); tag[x]=0; return ;}
    inline void rotate(int x){
        int y=fa[x],z=fa[y]; if(!isroot(y)) if(rs[z]==y) rs[z]=x; else ls[z]=x; 
        if(ls[y]==x) ls[y]=rs[x],fa[rs[x]]=y,rs[x]=y; 
        else rs[y]=ls[x],fa[ls[x]]=y,ls[x]=y; fa[x]=z; fa[y]=x;
        return push_up(y),push_up(x);    
    }
    int st[N],top;
    inline void splay(int x){
        int y=x; st[top=1]=y; while(!isroot(y)) st[++top]=y=fa[y];
        while(top) push_down(st[top--]); 
        while(!isroot(x)){
            y=fa[x]; int z=fa[y]; 
            if(!isroot(y)) rotate((ls[y]==x)^(ls[z]==y)?x:y); rotate(x); 
        } return push_up(x);
    }
    inline void access(int x){for(reg int y=0;x;x=fa[y=x]) splay(x),rs[x]=y,push_up(x); return ;}
    inline void makeroot(int x){access(x); splay(x);  pushr(x); return ;}
    inline int findroot(int x){access(x); splay(x); while(ls[x]) push_down(x),x=ls[x]; return splay(x),x;}
    inline void split(int x,int y){return makeroot(x),access(y),splay(y);}
    inline void link(int x,int y){makeroot(x); if(findroot(y)!=x) fa[x]=y; return;}
    inline void cut(int x,int y){makeroot(x); if(findroot(y)!=x||fa[y]!=x||ls[y]) return ; rs[x]=fa[y]=0; push_up(x); return ;} 
    char s[10];
    signed main(){
        n=read(); Q=read(); read();
        for(reg int i=1;i<=n;++i) tp[i]=read(),scanf("%lf%lf",&a[i],&b[i]),push_up(i);
        while(Q--){
            scanf("%s",s+1); //cout<<(s+1)<<endl;
            if(s[1]=='a') link(read()+1,read()+1);
            if(s[1]=='d') cut(read()+1,read()+1);
            if(s[1]=='m'){
                int x=read()+1; tp[x]=read(); scanf("%lf%lf",&a[x],&b[x]); makeroot(x); push_up(x); 
            }if(s[1]=='t'){
                int u=read()+1,v=read()+1; double x; scanf("%lf",&x); 
                if(findroot(u)!=findroot(v)) puts("unreachable");
                else split(u,v),printf("%.15lf
",query(x,v));
            }
        } return 0;
    }
}
signed main(){return yspm::main();}
原文地址:https://www.cnblogs.com/yspm/p/14354052.html