「THUWC2017」在美妙的数学王国中畅游 - 动态树LCT+生成函数+泰勒展开 | Bill Yang's Blog

「THUWC2017」在美妙的数学王国中畅游 - 动态树LCT+生成函数+泰勒展开

题目大意






题目分析

第一眼不可做题。(KEKE:这不是一眼题吗)
考虑部分分,$x=1$时很好做,直接用LCT求和即可。
对于所有数据点,若直接做是无法将这三种函数进行合并的,若不合并就带有参数$x$,不好做。
注意下面有个神奇的【小R教你学数学】的提示。(achen:就算他不给我提示我也做得出来)

其中$x_0$在连续区间中可以任意取值,$\epsilon$也可以任意取值(achen:一般取$1$)。

2018/1/29 update:现在不给我提示我也会做了,泰勒公式的推导可以看这里
2019/6/20 update:实际上题目给的提示是错的,$\epsilon$不能任意取值,$\epsilon$也不能等于$x$或者$x_0$,$\epsilon$是$x$与$x_0$之间的一个未知的数,不过这并不妨碍解题(见下述)。

显然,题目给出的函数求和在定义域上是连续的。
因为$i!$在$i\gt10$时就已经超过精度范围(相对误差),因此上式$n$只需要计算到$10$即可,且余项也可以忽略。
观察这个式子,发现若指定$x_0,\epsilon$是一个定值,函数中的参数就没了,只剩下$\frac{(x-x_0)^i}{i!}$这一部分,若可以快速得到$f^i(x_0)$,那么我们就可以付出$10$的常数求出答案。
因此我们只需要考虑求出一个函数的$i(i\in[0,10])$阶导数(可以看做一个长度为$11$的生成函数),其中$0$阶导数记为该函数本身,然后使用LCT将其合并起来即可。

对于函数$f(x)=\sin(ax+b)$,其一阶导数为$f’(x)=a\cos(ax+b)$,其二阶导数为$f’’(x)=-a^2\sin(ax+b)$,以此类推。
对于函数$f(x)=e^{ax+b}$,其一阶导数为$f’(x)=ae^{ax+b}$,以此类推。
对于一次函数$f(x)=ax+b$,其一阶导数为$a$,其2阶以上导数均为$0$。

然后就可以算了,其实也没那么难嘛。
$\epsilon,x_0$建议取区间$(0,1)$间,取$0.5$时误差较小。


代码

正常版程序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=100005,LIMIT=10;
const double x0=0.5;

int n,m,type2;
char type1;

int Type[maxn];
double A[maxn],B[maxn];

struct Link_Cut_Tree {
struct Tree {
int father,child[2];
bool rev;
double sum[LIMIT];
} tree[maxn];
stack<int>S;
#define fa(x) tree[x].father
#define ls(x) tree[x].child[0]
#define rs(x) tree[x].child[1]
#define rev(x) tree[x].rev
bool isroot(int index) {
return ls(fa(index))!=index&&rs(fa(index))!=index;
}
bool checkson(int index) {
return rs(fa(index))==index;
}
void push_down(int index) {
if(!rev(index))return;
swap(ls(index),rs(index));
rev(ls(index))^=1;
rev(rs(index))^=1;
rev(index)=0;
}
void push_up(int index) {
double a=A[index],b=B[index];
if(Type[index]==1) {
tree[index].sum[0]=sin(a*x0+b);
tree[index].sum[1]=cos(a*x0+b)*a;
for(int i=2; i<LIMIT; i++)tree[index].sum[i]=tree[index].sum[i-2]*(-a*a);
} else if(Type[index]==2) {
tree[index].sum[0]=exp(x0*a+b);
for(int i=1; i<LIMIT; i++)tree[index].sum[i]=tree[index].sum[i-1]*a;
} else {
tree[index].sum[0]=x0*a+b;
tree[index].sum[1]=a;
for(int i=2; i<LIMIT; i++)tree[index].sum[i]=0;
}
for(int i=0; i<LIMIT; i++)tree[index].sum[i]+=tree[ls(index)].sum[i]+tree[rs(index)].sum[i];
}
void rotate(int index) {
int father=fa(index),grand=fa(father),side=checkson(index);
if(!isroot(father))tree[grand].child[checkson(father)]=index;
tree[father].child[side]=tree[index].child[side^1];
fa(tree[father].child[side])=father;
fa(father)=index;
tree[index].child[side^1]=father;
fa(index)=grand;
push_up(father);
push_up(index);
}
void splay(int index) {
S.push(index);
for(int i=index; !isroot(i); i=fa(i))S.push(fa(i));
while(!S.empty())push_down(S.top()),S.pop();
for(int father; !isroot(index); rotate(index)) {
father=fa(index);
if(!isroot(father))rotate(checkson(index)==checkson(father)?father:index);
}
}
void access(int index) {
for(int son=0; index; son=index,index=fa(index)) {
splay(index);
rs(index)=son;
push_up(index);
}
}
void reverse(int index) {
access(index);
splay(index);
rev(index)^=1;
}
void link(int x,int y) {
reverse(x);
fa(x)=y;
}
void split(int x,int y) {
reverse(x);
access(y);
splay(y);
}
void cut(int x,int y) {
split(x,y);
ls(y)=fa(x)=0;
}
void modify(int index) {
splay(index);
push_up(index);
}
int get_root(int index) {
access(index);
splay(index);
int u=index;
while(ls(u))u=ls(u);
splay(u);
return u;
}
} lct;

int main() {
n=Get_Int();
m=Get_Int();
while(!isalpha(type1))type1=getchar();
type2=Get_Int();
for(int i=1; i<=n; i++) {
Type[i]=Get_Int();
scanf("%lf%lf",&A[i],&B[i]);
}
for(int i=1; i<=m; i++) {
char opt=' ';
while(!isalpha(opt))opt=getchar();
int x,y;
if(opt!='m')x=Get_Int()+1,y=Get_Int()+1;
if(opt=='a')lct.link(x,y);
else if(opt=='d')lct.cut(x,y);
else if(opt=='m') {
int pos=Get_Int()+1;
Type[pos]=Get_Int();
scanf("%lf%lf",&A[pos],&B[pos]);
lct.modify(pos);
} else {
double X;
scanf("%lf",&X);
if(lct.get_root(x)!=lct.get_root(y)) {
puts("unreachable");
continue;
}
lct.split(x,y);
double ans=0,up=1,down=1;
for(int i=0; i<LIMIT; i++) {
ans+=lct.tree[y].sum[i]*up/down;
up*=X-x0;
down*=i+1;
}
printf("%0.8le\n",ans);
}
}
return 0;
}

如果你想跑的更快,可以用这个部分分优化版。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

int n,m,type2;
char type1;

namespace Solve1 {
const int maxn=100005;

struct Tree {
int father,child[2];
bool rev;
double val,sum;
};

struct Link_Cut_Tree {
Tree tree[maxn];
stack<int>S;
#define fa(x) tree[x].father
#define ls(x) tree[x].child[0]
#define rs(x) tree[x].child[1]
#define rev(x) tree[x].rev
bool isroot(int index) {
return ls(fa(index))!=index&&rs(fa(index))!=index;
}
bool checkson(int index) {
return rs(fa(index))==index;
}
void push_down(int index) {
if(!rev(index))return;
swap(ls(index),rs(index));
rev(ls(index))^=1;
rev(rs(index))^=1;
rev(index)=0;
}
void push_up(int index) {
tree[index].sum=tree[ls(index)].sum+tree[rs(index)].sum+tree[index].val;
}
void rotate(int index) {
int father=fa(index),grand=fa(father),side=checkson(index);
if(!isroot(father))tree[grand].child[checkson(father)]=index;
tree[father].child[side]=tree[index].child[side^1];
fa(tree[father].child[side])=father;
fa(father)=index;
tree[index].child[side^1]=father;
fa(index)=grand;
push_up(father);
push_up(index);
}
void splay(int index) {
S.push(index);
for(int i=index; !isroot(i); i=fa(i))S.push(fa(i));
while(!S.empty())push_down(S.top()),S.pop();
for(int father; !isroot(index); rotate(index)) {
father=fa(index);
if(!isroot(father))rotate(checkson(index)==checkson(father)?father:index);
}
}
void access(int index) {
for(int son=0; index; son=index,index=fa(index)) {
splay(index);
rs(index)=son;
push_up(index);
}
}
void reverse(int index) {
access(index);
splay(index);
rev(index)^=1;
}
void link(int x,int y) {
reverse(x);
fa(x)=y;
}
void split(int x,int y) {
reverse(x);
access(y);
splay(y);
}
void cut(int x,int y) {
split(x,y);
ls(y)=fa(x)=0;
}
void modify(int index,double val) {
splay(index);
tree[index].val=val;
push_up(index);
}
int get_root(int index) {
access(index);
splay(index);
int u=index;
while(ls(u))u=ls(u);
return u;
}
} lct;

void solve() {
for(int i=1; i<=n; i++) {
int type=Get_Int();
double a,b;
scanf("%lf%lf",&a,&b);
if(type==1)lct.tree[i].val=lct.tree[i].sum=sin(a+b);
else if(type==2)lct.tree[i].val=lct.tree[i].sum=exp(a+b);
else lct.tree[i].val=lct.tree[i].sum=a+b;
}
for(int i=1; i<=m; i++) {
char opt=' ';
while(!isalpha(opt))opt=getchar();
int x,y;
if(opt!='m')x=Get_Int()+1,y=Get_Int()+1;
if(opt=='a')lct.link(x,y);
else if(opt=='d')lct.cut(x,y);
else if(opt=='m') {
int pos=Get_Int()+1,type=Get_Int();
double a,b;
scanf("%lf%lf",&a,&b);
if(type==1)lct.modify(pos,sin(a+b));
else if(type==2)lct.modify(pos,exp(a+b));
else lct.modify(pos,a+b);
} else {
Get_Int();
if(lct.get_root(x)!=lct.get_root(y)) {
puts("unreachable");
continue;
}
lct.split(x,y);
printf("%0.8le\n",lct.tree[y].sum);
}
}
}
}

namespace Solve2 {
const int maxn=100005,LIMIT=10;
const double x0=0.5;

int Type[maxn];
double A[maxn],B[maxn];

struct Link_Cut_Tree {
struct Tree {
int father,child[2];
bool rev;
double sum[LIMIT];
} tree[maxn];
stack<int>S;
#define fa(x) tree[x].father
#define ls(x) tree[x].child[0]
#define rs(x) tree[x].child[1]
#define rev(x) tree[x].rev
bool isroot(int index) {
return ls(fa(index))!=index&&rs(fa(index))!=index;
}
bool checkson(int index) {
return rs(fa(index))==index;
}
void push_down(int index) {
if(!rev(index))return;
swap(ls(index),rs(index));
rev(ls(index))^=1;
rev(rs(index))^=1;
rev(index)=0;
}
void push_up(int index) {
double a=A[index],b=B[index];
if(Type[index]==1) {
tree[index].sum[0]=sin(a*x0+b);
tree[index].sum[1]=cos(a*x0+b)*a;
for(int i=2; i<LIMIT; i++)tree[index].sum[i]=tree[index].sum[i-2]*(-a*a);
} else if(Type[index]==2) {
tree[index].sum[0]=exp(x0*a+b);
for(int i=1; i<LIMIT; i++)tree[index].sum[i]=tree[index].sum[i-1]*a;
} else {
tree[index].sum[0]=x0*a+b;
tree[index].sum[1]=a;
for(int i=2; i<LIMIT; i++)tree[index].sum[i]=0;
}
for(int i=0; i<LIMIT; i++)tree[index].sum[i]+=tree[ls(index)].sum[i]+tree[rs(index)].sum[i];
}
void rotate(int index) {
int father=fa(index),grand=fa(father),side=checkson(index);
if(!isroot(father))tree[grand].child[checkson(father)]=index;
tree[father].child[side]=tree[index].child[side^1];
fa(tree[father].child[side])=father;
fa(father)=index;
tree[index].child[side^1]=father;
fa(index)=grand;
push_up(father);
push_up(index);
}
void splay(int index) {
S.push(index);
for(int i=index; !isroot(i); i=fa(i))S.push(fa(i));
while(!S.empty())push_down(S.top()),S.pop();
for(int father; !isroot(index); rotate(index)) {
father=fa(index);
if(!isroot(father))rotate(checkson(index)==checkson(father)?father:index);
}
}
void access(int index) {
for(int son=0; index; son=index,index=fa(index)) {
splay(index);
rs(index)=son;
push_up(index);
}
}
void reverse(int index) {
access(index);
splay(index);
rev(index)^=1;
}
void link(int x,int y) {
reverse(x);
fa(x)=y;
}
void split(int x,int y) {
reverse(x);
access(y);
splay(y);
}
void cut(int x,int y) {
split(x,y);
ls(y)=fa(x)=0;
}
void modify(int index) {
splay(index);
push_up(index);
}
int get_root(int index) {
access(index);
splay(index);
int u=index;
while(ls(u))u=ls(u);
splay(u);
return u;
}
} lct;

void solve() {
for(int i=1; i<=n; i++) {
Type[i]=Get_Int();
scanf("%lf%lf",&A[i],&B[i]);
}
for(int i=1; i<=m; i++) {
char opt=' ';
while(!isalpha(opt))opt=getchar();
int x,y;
if(opt!='m')x=Get_Int()+1,y=Get_Int()+1;
if(opt=='a')lct.link(x,y);
else if(opt=='d')lct.cut(x,y);
else if(opt=='m') {
int pos=Get_Int()+1;
Type[pos]=Get_Int();
scanf("%lf%lf",&A[pos],&B[pos]);
lct.modify(pos);
} else {
double X;
scanf("%lf",&X);
if(lct.get_root(x)!=lct.get_root(y)) {
puts("unreachable");
continue;
}
lct.split(x,y);
double ans=0,up=1,down=1;
for(int i=0; i<LIMIT; i++) {
ans+=lct.tree[y].sum[i]*up/down;
up*=X-x0;
down*=i+1;
}
printf("%0.8le\n",ans);
}
}
}
}

int main() {
n=Get_Int();
m=Get_Int();
while(!isalpha(type1))type1=getchar();
type2=Get_Int();
if(type2==0)Solve1::solve();
else Solve2::solve();
return 0;
}

姥爷们赏瓶冰阔落吧~
0%