传送门

当年听llj讲的时候觉得这简直是个不可做的神题.

现在看来并不是很神,可能是我已经被剧透了的缘故...

一开始以为是函数套函数,懵蔽了好久,结果只是求和

被剧透了泰勒展开就比较水了..只要你不像我一样蠢的最最简单的求导都求错...

还有不像我一样蠢展开了看到有常数项不暴力二项式定理展开转而展开f(a*x+b)发现不会求e^b...

那么直接泰勒展开然后二项式定理暴力展开后用lct合并即可,维护个17项就差不多了

 //Achen
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
const int N=+;
typedef long long LL;
typedef double db;
using namespace std;
int n,m;
char o[];
db C[][],inv[],a_i[],b_i[]; template<typename T>void read(T &x) {
char ch=getchar(); x=; T f=;
while(ch!='-'&&(ch<''||ch>'')) ch=getchar();
if(ch=='-') f=-,ch=getchar();
for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;
} int ch[N][],p[N],flip[N];
#define lc ch[x][0]
#define rc ch[x][1]
struct data {
db a[];
friend data operator +(const data&A,const data&B) {
data rs;
For(i,,) rs.a[i]=A.a[i]+B.a[i];
return rs;
}
}dt[N],sum[N]; int isroot(int x) {return (ch[p[x]][]!=x&&ch[p[x]][]!=x);} void update(int x) { sum[x]=dt[x]+sum[lc]+sum[rc]; } void down(int x) {
if(!flip[x]) return;
swap(lc,rc);
flip[x]^=;
flip[lc]^=;
flip[rc]^=;
} void rotate(int x) {
int y=p[x],z=p[y],l=(x==ch[y][]),r=l^;
if(!isroot(y)) ch[z][y==ch[z][]]=x; p[x]=z;
ch[y][l]=ch[x][r]; p[ch[x][r]]=y;
ch[x][r]=y; p[y]=x;
update(y); update(x);
} void splay(int x) {
static int g[N],top=,tp;
for(tp=x;!isroot(tp);tp=p[tp]) g[++top]=tp;
g[++top]=tp;
while(top) {down(g[top--]);}
for(;!isroot(x);rotate(x)) {
int y=p[x],z=p[y];
if(!isroot(y))
((x==ch[y][])^(y==ch[z][]))?rotate(x):rotate(y);
}
} void access(int x) {
for(int t=;x;x=p[t=x]) {
splay(x);
rc=t;
update(x);
}
} int find_root(int x) {
access(x);
splay(x);
while(lc) x=lc;
return x;
} void newroot(int x) {
access(x);
splay(x);
flip[x]^=;
} void lik(int x,int y) {
if(find_root(x)==find_root(y)) return;
newroot(x);
splay(x);
p[x]=y;
} void cut(int x,int y) {
newroot(x);
access(y);
splay(y);
if(ch[y][]==x) ch[y][]=p[x]=; update(y);
} void get_it(data &tp,int f,db a,db b) {
For(i,,) tp.a[i]=;
if(f==) { //sin(a*x+b);
a_i[]=b_i[]=;
For(i,,) a_i[i]=a_i[i-]*a,b_i[i]=b_i[i-]*b;
db f=1.0;
for(int i=;i<=;i+=,f=-f)
For(j,,i) tp.a[j]+=f*inv[i]*a_i[j]*b_i[i-j]*C[i][j];
}
else if(f==) { //e^(a*x+b);
a_i[]=b_i[]=;
For(i,,) a_i[i]=a_i[i-]*a,b_i[i]=b_i[i-]*b;
For(i,,) For(j,,i)
tp.a[j]+=inv[i]*a_i[j]*b_i[i-j]*C[i][j];
}
else tp.a[]=b,tp.a[]=a;
} db calc(data tp,db x) {
db rs=,now=;
For(i,,) {
rs=rs+tp.a[i]*now;
now*=x;
}
return rs;
} void change(int x,int f,db a,db b) {
splay(x);
get_it(dt[x],f,a,b);
update(x);
} void qry(int x,int y,db z) {
if(find_root(x)!=find_root(y)) {
puts("unreachable");
return;
}
newroot(x);
access(y);
splay(y);
printf("%.8le\n",calc(sum[y],z));
} //#define DEBUG
int main() {
#ifdef DEBUG
freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
#endif
read(n); read(m); scanf("%s",o);
For(i,,) C[i][]=;
For(i,,) For(j,,i) C[i][j]=C[i-][j]+C[i-][j-];
inv[]=inv[]=;
For(i,,) inv[i]=inv[i-]/(1.0*i);
for(int i=;i<=n;i++) {
int f; db a,b;
scanf("%d %lf %lf",&f,&a,&b);
get_it(dt[i],f,a,b);
}
while(m--) {
scanf("%s",o);
if(o[]=='a') {
int x,y; read(x); read(y);
lik(x+,y+);
}
else if(o[]=='d') {
int x,y; read(x); read(y); cut(x+,y+);
}
else if(o[]=='m') {
int x,f; db a,b;
scanf("%d %d %lf %lf",&x,&f,&a,&b);
change(x+,f,a,b);
}
else if(o[]=='t') {
int x,y; db z;
scanf("%d %d %lf",&x,&y,&z);
qry(x+,y+,z);
}
}
return ;
}

最新文章

  1. DateTime 详解
  2. Post方式的Http流请求调用
  3. 设计模式学习之中介者模式(Mediator,行为型模式)(18)
  4. php 中如何创建一个空对象
  5. MERGE 用法
  6. nginx demo
  7. Oracle数据库启动流程
  8. Android layoutInflate.inflate 方法具体解释,removeView()错误解决
  9. node.js 中模块的循环调用问题详解
  10. Postman基本使用——get、post请求、断言、环境变量
  11. Java并发系列[9]----ConcurrentHashMap源码分析
  12. issubclass判断前面是不是后面的子类
  13. 【一天一道LeetCode】 #1 Two Sum
  14. 2019.04.23 Scrapy框架
  15. Python 用下划线作为变量前缀和后缀指定特殊变量
  16. MIDAS.dll 出错时 (Error loading MIDAS.DLL.)
  17. linux_文件夹实现挂载(必须在同一网段)
  18. C++ Web 编程
  19. layer关闭弹出层,弹出打印
  20. git分支branch合并到主分支master

热门文章

  1. C++与JAVA语言区别
  2. 在KVM虚拟化中如何实现vlan
  3. codeforces1175E Minimal Segment Cover 倍增
  4. 笔记44 Hibernate快速入门(一)
  5. d3操作svg路径动画,及dom移动
  6. SQLServer2008上的SDE备份和还原
  7. Mac电脑最常见的办公软件是什么?Notion for Mac多功能办公笔记软件使用方法
  8. vue-cli3+ant-design-vue+typescript 注意事项
  9. pytorch实现kaggle猫狗识别
  10. 牛客多校第十场 F Popping Balloons 线段树维护稀疏矩阵