题解P4546【[THUWC2017]在美妙的数学王国中畅游】

· · 题解

LCT+泰勒展开

首先e^x求导完是ln e * e^x还是e^x

sin x求导完变成cos x，cos x求导完变成sin x

由于复合函数f(g(x))求导完是f'(g(x))*g'(x)

所以就可以轻松的推出sin x和e^x的n阶导数

对于泰勒展开的那个公式，我们发现x0=0.5时，每一项的系数为1/2/n!，到了后面对ans的影响非常小，可以忽略，于是我们只要把多项式的前14项提出来就好。

接下来动态树上的操作用Link Cut Tree维护一下就ok了

代码（有点长）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cassert>
#include <cmath>
#include <complex>
#include <bitset>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define rep(i, a, b) for(int (i) = (a), __omega = (b); (i) <= __omega; ++(i))
#define down(i, a, b) for(int (i) = (a), __omega = (b); (i) >= (b); --(i))
#define openfile(name) freopen(name".in", "r", stdin), freopen(name".out", "w", stdout)
using namespace std;

const double x0 = 0.5;

const int bit = 14;

double frac[20];

void init_frac() { frac[0] = 1; for(int i = 1; i <= bit; ++i) frac[i] = frac[i-1]*i; } //预处理阶乘 

//sin(x)的n阶导 
double diff_sin(int n, double x) {
    double k = ((n&3) == 0 || (n&3) == 1) ? 1 : -1;
    if(n&1) return k*cos(x); else return k*sin(x);
}

struct poly {
    double a[20];
    friend poly operator+(poly a, poly b) {
        for(int i = bit; ~i; --i) a.a[i] += b.a[i]; return a;
    }
    double operator()(double x) {
        x -= x0; double res = 0;
        for(int i = bit; ~i; --i) res *= x, res += a[i];
        return res;
    }
    void get_line(double A, double B) {
        memset(a, 0, sizeof(double)*20);
        a[0] = B+x0*A; a[1] = A;
    }
    void get_sin(double A, double B) {
        memset(a, 0, sizeof(double)*20);
        double xx = A*x0+B;
        double an = 1;
        for(int i = 0; i <= bit; ++i) {
            a[i] = an*diff_sin(i, xx)/frac[i];
            an = an*A;
        }
    }
    void get_exp(double A, double B) {
        memset(a, 0, sizeof(double)*20);
        double xx = A*x0+B;
        double an = 1;
        for(int i = 0; i <= bit; ++i) {
            a[i] = an*exp(xx)/frac[i];
            an = an*A;
        }
    }
}; 

struct node *nul;

struct node {

    node *son[2], *top, *fa;

    poly val, sum;

    int rev;

    void reverse() { rev ^= 1; swap(son[0], son[1]);  }

    void push_up() { sum = val+(son[0]->sum)+(son[1]->sum); }

    void push_down() {
        if(rev) {
            rev ^= 1;
            son[0]->reverse();
            son[1]->reverse();
        }
    }

    int pos() { return fa->son[1] == this; }

    void rotate() {
        int d = pos(); node *y = fa; 
        y->push_down(); push_down();
        top = y->top;
        if(y->fa != nul) y->fa->son[y->pos()] = this;
        y->son[d] = son[d^1], son[d^1] = y;
        if(y->son[d] != nul) y->son[d]->fa = y;
        fa = y->fa, y->fa = this;
        y->push_up(), push_up();
    }

    void splay() {
        push_down();
        for(node *y = fa; fa != nul; rotate())
            if(y = fa, y->fa != nul) y->pos()^pos() ? rotate() : y->rotate();
        push_up();
    }

    void expose(node *p = nul) {
        splay();
        if(son[1] != nul) {
            son[1]->fa = nul;
            son[1]->top = this;
        }
        son[1] = p;
        if(p != nul) p->fa = this;
        push_up();
    }

} pos[100010];

node *access(node *x) {
    for(x->expose(); x->top; x = x->top) x->top->expose(x);
    return x;
}

void link(node *x, node *y) { x = access(x); x->reverse(); x->top = y; }

void cut(node *x, node *y) {
    x->expose(), y->expose();
    if(x->top == y) x->top = 0;
    if(y->top == x) y->top = 0;
}

node *root(node *x) {
    x = access(x);
    for(; x->son[0] != nul; x = x->son[0]);
    return x;
}

int n, m;

poly p[100010];

char spe[5];

int main() {
    init_frac();
    scanf("%d%d%s", &n, &m, spe);
    nul = pos;
    for(int i = 0; i <= n; ++i) {
        (pos+i)->fa = (pos+i)->son[0] = (pos+i)->son[1] = nul;
    }
    for(int i = 1; i <= n; ++i) {
        int type; double a, b;
        scanf("%d%lf%lf", &type, &a, &b);
        if(type == 1) {
            p[i].get_sin(a, b);
        } else if(type == 2) {
            p[i].get_exp(a, b);
        } else if(type == 3) {
            p[i].get_line(a, b);
        }
        (pos+i)->val = (pos+i)->sum = p[i];
    } 
    while(m--) {
        static char str[20];
        scanf("%s", str);
        if(!strcmp(str, "appear")) {
            int u, v;
            scanf("%d%d", &u, &v);
            u++, v++;
            link(pos+u, pos+v);
        } else if(!strcmp(str, "disappear")) {
            int u, v;
            scanf("%d%d", &u, &v);
            u++, v++;
            cut(pos+u, pos+v);
        } else if(!strcmp(str, "magic")) {
            int c, f; double a, b;
            scanf("%d%d%lf%lf", &c, &f, &a, &b);
            c++;
            if(f == 1) {
                p[c].get_sin(a, b);
            } else if(f == 2) {
                p[c].get_exp(a, b);
            } else if(f == 3) {
                p[c].get_line(a, b);
            }
            access(pos+c);
            (pos+c)->sum = (pos+c)->val = p[c];
        } else if(!strcmp(str, "travel")) {
            int u, v; double x;
            scanf("%d%d%lf", &u, &v, &x);
            u++, v++;
            if(root(pos+u) != root(pos+v)) {
                puts("unreachable");
            } else {
                access(pos+u);
                (pos+u)->splay();
                (pos+u)->reverse();
                poly f = access(pos+v)->sum;
                printf("%.9lf\n", f(x));
            }
        } else {
            puts("orz fjzzq2002!");
        }
    }
    return 0;
}