bzoj5020 & loj2289 [THUWC 2017]在美妙的数学王国中畅游 LCT + 泰勒展开

题目传送门

https://lydsy.com/JudgeOnline/problem.php?id=5020

https://loj.ac/problem/2289

题解

这个 appear 和 disappear 操作显然是强行加上去用力啊增加代码长度的。

所以相当于就是什么东西套个 LCT 就行了。

所以考虑怎么快速求出一堆东西的分值和。

\(sin, exp\)，一次函数之间的加法似乎并没有什么优美的性质，所以我们考虑泰勒展开。

\[e^v = \sum_{i=0}^{\infty} \frac1{i!} \cdot v^i
\]

我们把 \(v=ax+b\) 带进去，就是

\[\begin{align*}e^v &= \sum_{i=0}^{\infty} \frac1{i!} \cdot (ax+b)^i\\&= \sum_{i=0}^{\infty} \frac1{i!} \sum_{j=0}^i \binom ij a^jb^{i-j}x^j\\&= \sum_{j=0}^{\infty}a^jx^j \sum_{i=j}^{\infty} \frac{\binom ij b^{i-j}}{i!}\end{align*}
\]

这样我们就可以求出每一个 \(x^i\) 前面的系数了。

\(sin\) 的话同理，就不重新写一遍了。一次函数的话 \(x^i\) 前面的系数根本不用算。

大概展开十几项就够了，这里开了 \(16\) 项。

这样话时间复杂度就是 \(O(m(16\log n+16^2))\)。

#include<bits/stdc++.h>

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)

#define dbg(...) fprintf(stderr, __VA_ARGS__)

#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)

#define fi first

#define se second

#define pb push_back

template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}

template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;}

typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;

template<typename I> inline void read(I &x) {

	int f = 0, c;

	while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;

	x = c & 15;

	while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);

	f ? x = -x : 0;

}

const int N = 100000 + 7;

const int M = 16;

#define lc c[0]

#define rc c[1]

int n, m;

ll fac[M], C[M][M];

struct Node {

	int c[2], fa, rev;

	double v[M], sum[M];

	inline Node() {}

	inline void set(const int &f, const double &a, const double &b) {

		memset(v, 0, sizeof(v));

		if (f == 1) {

			double aa = 1;

			for (int i = 0; i < M; ++i) {

				double bb = 1;

				for (int j = i; j < M; ++j, bb *= b)

					if ((j & 1) && (j >> 1) & 1) v[i] -= C[j][i] * bb / fac[j];

					else if ((j & 1) && !((j >> 1) & 1)) v[i] += C[j][i] * bb / fac[j];

				v[i] *= aa, aa *= a;

			}

		} else if (f == 2) {

			double aa = 1;

			for (int i = 0; i < M; ++i) {

				double bb = 1;

				for (int j = i; j < M; ++j, bb *= b) v[i] += C[j][i] * bb / fac[j];

				v[i] *= aa, aa *= a;

			}

		} else if (f == 3) v[0] = b, v[1] = a;

	}

} t[N];

int st[N];

inline bool idtfy(int o) { return t[t[o].fa].rc == o; }

inline bool isroot(int o) { return t[t[o].fa].lc != o && t[t[o].fa].rc != o; }

inline void connect(int fa, int o, int d) { t[fa].c[d] = o, t[o].fa = fa; }

inline void pushup(int o) {

	assert(o);

	assert(!t[o].rev);

	for (int i = 0; i < M; ++i)

		t[o].sum[i] = t[t[o].lc].sum[i] + t[t[o].rc].sum[i] + t[o].v[i];

}

inline void pushdown(int o) {

	if (!t[o].rev) return;

	if (t[o].lc) t[t[o].lc].rev ^= 1, std::swap(t[t[o].lc].lc, t[t[o].lc].rc);

	if (t[o].rc) t[t[o].rc].rev ^= 1, std::swap(t[t[o].rc].lc, t[t[o].rc].rc);

	t[o].rev = 0;

}

inline void rotate(int o) {

	assert(!isroot(o));

	int fa = t[o].fa, pa = t[fa].fa, d1 = idtfy(o), d2 = idtfy(fa), b = t[o].c[d1 ^ 1];

	if (!isroot(fa)) t[pa].c[d2] = o; t[o].fa = pa;

	connect(o, fa, d1 ^ 1), connect(fa, b, d1);

	pushup(fa), pushup(o);

	assert(!t[0].lc && !t[0].rc);

}

inline void splay(int o) {

	int x = o, tp = 0;

	st[++tp] = x;

	while (!isroot(x)) st[++tp] = x = t[x].fa;

	while (tp) pushdown(st[tp--]);

	while (!isroot(o)) {

		int fa = t[o].fa;

		if (isroot(fa)) rotate(o);

		else if (idtfy(o) == idtfy(fa)) rotate(fa), rotate(o);

		else rotate(o), rotate(o);

	}

}

inline void access(int o) {

	for (int x = 0; o; o = t[x = o].fa)

		splay(o), t[o].rc = x, pushup(o);

}

inline void mkrt(int o) {

	access(o), splay(o);

	t[o].rev ^= 1, std::swap(t[o].lc, t[o].rc);

}

inline int getrt(int o) {

	access(o), splay(o);

	while (pushdown(o), t[o].lc) o = t[o].lc;

	return splay(o), o;

}

inline void link(int x, int y) {

	mkrt(x);

	if (getrt(y) != x) t[x].fa = y;

	else assert(0);

}

inline void cut(int x, int y) {

	mkrt(x), access(y), splay(y);

	if (t[y].lc == x && !t[x].rc) t[x].fa = t[y].lc = 0, pushup(y);

	else assert(0);

}

inline void work() {

	while (m--) {

		char opt[10];

		scanf("%s", opt);

		if (*opt == 'a') {

			int x, y;

			read(x), read(y);

			++x, ++y;

			link(x, y);

		} else if (*opt == 'd') {

			int x, y;

			read(x), read(y);

			++x, ++y;

			cut(x, y);

		} else if (*opt == 'm') {

			double a, b;

			int x, opt;

			read(x), read(opt), scanf("%lf%lf", &a, &b);

			++x;

			splay(x), t[x].set(opt, a, b), pushup(x);

		} else {

			int x, y;

			double v, vv = 1, ans = 0;

			read(x), read(y), scanf("%lf", &v);

			++x, ++y;

			if (getrt(x) != getrt(y)) { puts("unreachable"); continue; }

			mkrt(x), access(y), splay(y);

			for (int i = 0; i < M; ++i, vv *= v) ans += vv * t[y].sum[i];

			printf("%.8le\n", ans);

		}

	}

}

inline void init() {

	read(n), read(m);

	fac[0] = 1;

	for (int i = 1; i < M; ++i) fac[i] = fac[i - 1] * i;

	C[0][0] = 1;

	for (int i = 1; i < M; ++i) {

		C[i][0] = 1;

		for (int j = 1; j < M; ++j) C[i][j] = C[i - 1][j - 1] + C[i - 1][j];

	}

	int opt;

	double a, b;

	read(opt);

	for (int i = 1; i <= n; ++i) read(opt), scanf("%lf%lf", &a, &b), t[i].set(opt, a, b), pushup(i);

}

int main() {

#ifdef hzhkk

	freopen("hkk.in", "r", stdin);

#endif

	init();

	work();

	fclose(stdin), fclose(stdout);

	return 0;

}

巴特西

bzoj5020 & loj2289 [THUWC 2017]在美妙的数学王国中畅游 LCT + 泰勒展开

题目传送门

题解

最新文章

热门文章