loj#2289. 「THUWC 2017」在美妙的数学王国中畅游

loj#2289. 「THUWC 2017」在美妙的数学王国中畅游

原题传送门:>Here<

这道题乍一看很高端,其实只要瞎JB泰勒展开一下再维护一下前几项的值就好了。。。

我们考虑对三个函数泰勒展开:

接下来就是基本$LCT$处理了。

代码:

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
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=100001,P=11;
long double sum[N][P],val[N][P],fac[P];
int ch[N][2],fa[N],n,m;
bool lazy[N];
inline void pushup(const int &x){for(int i=0;i<P;i++)sum[x][i]=sum[ch[x][0]][i]+sum[ch[x][1]][i]+val[x][i];}
inline bool son(const int &x){return ch[fa[x]][1]==x;}
inline bool isroot(const int &x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
void Rotate(const int &x){
// printf("%d\n",x);
if(!x||!fa[x])return;
int faz=fa[x],fazz=fa[faz],g=son(x);
fa[x]=fazz;
if(!isroot(faz))ch[fazz][son(faz)]=x;
ch[faz][g]=ch[x][!g];
fa[ch[x][!g]]=faz;
ch[x][!g]=faz;
fa[faz]=x;
pushup(faz);
pushup(x);
}
void spread(int x){
if(!lazy[x])return;
swap(ch[x][0],ch[x][1]);
lazy[ch[x][0]]^=1;
lazy[ch[x][1]]^=1;
lazy[x]=0;
}
inline void clear(const int &x){
if(!isroot(x))clear(fa[x]);
spread(x);
}
void splay(int x){
// printf("splay %d\n",x);
clear(x);
while(!isroot(x)){
if(!isroot(fa[x])){
if(son(fa[x])^son(x))Rotate(x);
else Rotate(fa[x]);
}
Rotate(x);
}
}
void access(int x){
// printf("access\n");
for(int y=0;x;y=x,x=fa[x])
splay(x),ch[x][1]=y,pushup(x);
}
void mroot(int x){
access(x);
splay(x);
lazy[x]^=1;
}
void split(int x,int y){
mroot(x);
access(y);
splay(y);
}
void link(int x,int y){
mroot(x);
fa[x]=y;
}
void cut(int x,int y){
split(x,y);
if(ch[y][0]==x&&!ch[x][1])fa[x]=ch[y][0]=0,pushup(y);
}
int findroot(int x){
access(x);
splay(x);
while(ch[x][0])x=ch[x][0];
return x;
}
int read(){
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
void set(int x){
static int type;
type=read();
memset(val[x],0,sizeof val[x]);
if(type==1){
long double a,b;
scanf("%Lf%Lf",&a,&b);
val[x][0]=1.;
for(int i=1;i<P;i++)val[x][i]=val[x][i-1]*a;
for(int i=0;i<P;i++){
if(i&1)val[x][i]*=cos(b);
else val[x][i]*=sin(b);
val[x][i]/=fac[i];
if((i%4)>1)val[x][i]=-val[x][i];
}
}
else if(type==2){
long double a,b;
scanf("%Lf%Lf",&a,&b);
val[x][0]=1.;
for(int i=1;i<P;i++)val[x][i]=val[x][i-1]*a;
for(int i=0;i<P;i++){
val[x][i]*=exp(b);
val[x][i]/=fac[i];
}
}
else{
scanf("%LF%Lf",val[x]+1,val[x]);
}
}
char str[10];
int main(){
n=read(),m=read();
getchar(),getchar(),getchar();
fac[0]=1.;
for(int i=1;i<P;i++)fac[i]=fac[i-1]*(long double)i;
for(int i=1;i<=n;i++)set(i),pushup(i);
for(int i=1,t1,t2;i<=m;i++){
scanf("%s",str);
t1=read()+1;
if(str[0]!='m')t2=read()+1;
if(str[0]=='a')link(t1,t2);
else if(str[0]=='d')cut(t1,t2);
else if(str[0]=='t'){
long double ans=0.,t3,t4=1.;
scanf("%Lf",&t3);
if(findroot(t1)!=findroot(t2)){
puts("unreachable");
continue;
}
split(t1,t2);
for(int j=0;j<P;j++)ans+=sum[t2][j]*t4,t4*=t3;
printf("%.8Lf\n",ans);
}
else{
splay(t1);
set(t1);
}
}
}
# LCT, 数学

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×