题解 P4546 【[THUWC2017]在美妙的数学王国中畅游】
Nemlit
2020-02-27 19:27:07
前置知识：$\rm LCT$, 简单求导，泰勒公式
我们知道，$\dfrac{dy}{dx}f(g(x))=\dfrac{dy}{dh}f(h)\times \dfrac{dh}{dx}g(x)$，然后可以对三种函数分开看：
对于一次函数（为了给下面两个复合函数一些启示，这里我把一次函数看成一个复合函数，求轻喷），我们可以令$f(x)=x, g(x)=ax+b$
我们先对其求一阶导，有$\dfrac{dy}{dx}f(g(x))=\dfrac{dy}{dh}f(h)\times \dfrac{dh}{dx}g(x)$，由于$f(x)$的导数是常数1，$g(x)$的导数是常数$a$，则有，$\dfrac{dy}{dx}f(g(x))=a$
然后对其求二阶导，发现二阶导数就变成$0$了，更高阶同理。于是这个东西的近似$\sum_{k=0}^\infty \dfrac{f^{k}(0)}{k!}x^k=ax+b$~~（好的我们有划回来了）~~
对于指数函数，根一次函数同理，令$f(x)=e^x, g(x)=ax+b$
同理，先求一阶导，有$\dfrac{dy}{dx}f(g(x))=a\times e^{ax+b}$，继续求其二阶导，发现之变化了一个$a$，有$\dfrac{d^2y}{dx^2}f(g(x))=a^2\times e^{ax+b}$继续求导，发现只是不断比上一阶多了一个$a$，于是我们有：$f^{k}=a^k\times e^{ax+b}$
根据泰勒公式，有$e^{ax+b}=\sum_{k=0}^\infty \dfrac{f^{k}(0)}{k!}x^k=\sum_{k=0}^\infty \dfrac{a^k\times e^b}{k!}x^k$。由于这道题只需要精确到7位小数，$k!$增长速度跟$n^n$类似（仅仅是一个比方），由于$a, b, x$都是$\in [0, 1]$，所以我们大概只需要处理20项就可以了
对于正弦函数，$\dfrac{dy}{dx}sin(x)=cos(x), \dfrac{dy}{dx}cos(x)=-sin(x)$。仍然令$f(x)=sin(x), g(x)=ax+b$，一阶导数为：$a \times cos(ax+b)$，再高一阶？$\dfrac{d^2y}{dx^2}=a^2*(-sin(ax+b))$。同理，我们有：$\dfrac{d^3y}{dx^3}=a^3*(-cos(ax+b))$，$\dfrac{d^4y}{dx^4}=a^4*sin(ax+b)$，不难发现，除了多带了一个$a^4$之外没有变化，于是这是一个长度为$4$的循环节。我们设这个循环节的函数为$h(x)$，有：$sin(ax+b)=\sum_{k=0}^\infty \dfrac{f^{k}(0)}{k!}x^k=\sum_{k=0}^\infty \dfrac{a^k\times h(b)}{k!}x^k$
柿子推完了，讲一下实现。我们发现这个$x^k$是可以提出来的，于是对于每一个$k$，用$\rm LCT$来维护一段区间的和，最后把所有答案合并即可。所涉及的都是$\rm LCT$的基本操作
### $\rm Code:$
```cpp
/* This code is written by Nemlit */
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define rep(i, a, b) for(re int i = (a); i <= (b); ++ i)
il int read() {
re int x = 0, f = 1; re char c = getchar();
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
return x * f;
}
#define maxn 200005
#define isroot(x) (ch[0][fa[x]] == x || ch[1][fa[x]] == x)
#define get_fa(x) (ch[1][fa[x]] == x)
#define updown(x) (swap(ch[0][x], ch[1][x]), tag[x] ^= 1)
int n, m, fa[maxn], ch[2][maxn], tag[maxn], st[maxn];
double sum[25][maxn], val[25][maxn], fac[maxn];
char c[maxn];
il void pushup(int x) { rep(i, 0, 20) sum[i][x] = sum[i][ch[0][x]] + sum[i][ch[1][x]] + val[i][x]; }
il void pushdown(int x) {
if(!tag[x]) return;
tag[x] ^= 1;
if(ch[0][x]) updown(ch[0][x]);
if(ch[1][x]) updown(ch[1][x]);
}
il void rotate(int x) {
int y = fa[x], z = fa[y], w = get_fa(x), k = get_fa(y);
if(isroot(y)) ch[k][z] = x;
if(ch[w ^ 1][x]) fa[ch[w ^ 1][x]] = y;
fa[x] = z, ch[w][y] = ch[w ^ 1][x], ch[w ^ 1][x] = y, fa[y] = x, pushup(y), pushup(x);
}
il void Splay(int x) {
int top = 0, u = x;
st[++ top] = u;
while(isroot(u)) st[++ top] = u = fa[u];
while(top) pushdown(st[top --]);
while(isroot(x)) {
if(isroot(fa[x])) rotate(get_fa(x) == get_fa(fa[x]) ? fa[x] : x);
rotate(x);
}
pushup(x);
}
il void access(int x) { for(re int y = 0; x; y = x, x = fa[x]) Splay(x), ch[1][x] = y, pushup(x); }
il int findroot(int x, int u = 0) {
access(x), Splay(x), u = x;
while(ch[0][u]) u = ch[0][u];
return Splay(u), u;
}
il void makeroot(int x) { access(x), Splay(x), updown(x); }
il void spilt(int x, int y) { makeroot(x), access(y), Splay(y); }
il void link(int x, int y) { makeroot(x), fa[x] = y; }
il void cut(int x, int y) { spilt(y, x), fa[y] = ch[0][x] = 0, pushup(x); }
il void solve(int i) {
int opt = read(); double x, y; scanf("%lf%lf", &x, &y);
if(opt == 1) {
double pax = 1, C = cos(y), S = sin(y);
rep(j, 0, 20) {
if(j % 2 == 0) val[j][i] = ((j % 4 == 0) ? 1 : -1) * S * pax / fac[j];
else val[j][i] = ((j % 4 == 1) ? 1 : -1) * C * pax / fac[j];
pax = pax * x;
}
}
if(opt == 2) {
double pax = 1.0, te = exp(y);
rep(j, 0, 20) val[j][i] = te * pax / fac[j], pax = pax * x;
}
if(opt == 3) {
val[0][i] = y, val[1][i] = x;
rep(j, 2, 20) val[j][i] = 0;
}
}
signed main() {
n = read(), m = read(), scanf("%s", c + 1), fac[0] = 1;
rep(i, 1, 20) fac[i] = fac[i - 1] * i;
rep(i, 1, n) solve(i);
while(m --) {
scanf("%s", c + 1);
if(c[1] == 'a') link(read() + 1, read() + 1);
if(c[1] == 'd') cut(read() + 1, read() + 1);
if(c[1] == 'm') {
int x = read() + 1;
Splay(x), solve(x), pushup(x);
}
if(c[1] == 't') {
int u = read() + 1, v = read() + 1; double ans = 0, pax = 1, x;
scanf("%lf", &x);
if(findroot(u) != findroot(v)) { puts("unreachable"); continue; }
spilt(u, v);
rep(i, 0, 20) ans += sum[i][v] * pax, pax *= x;
printf("%.10lf\n", ans);
}
}
return 0;
}
```