【校内模拟】水题（斐波那契通项公式）（LCT）

校内模拟】水题（斐波那契通项公式）（LCT）"/>

【校内模拟】水题（斐波那契通项公式）（LCT）

题意

从前有个斐波那契数列， 他不甘于生活在序列上，他决定做一个有梦想的数列，于是他找到了一棵树，想生活在一棵树上。但是树告诉他，你需要解决下面的问题，才能够有资格生活在树上。

· 给出一棵?个结点的树，以1为根，点?有权值为??，进行?次操作，有4种操作：

1. 给出?, ?,将?的父亲改成?
2. 给出?, ?, ?,将路径? → ?上的点权值全改成?
3. 给出?,询问?(??)
4. 给出?, ?,对于路径? → ?,假设路径上的点权值分别是?1, ?2 … ??,求出下面式子的值：

∑ i = 1 k ∑ j = i k F ( ∑ p = i j b p ) \sum_{i=1}^k \sum_{j=i}^k F(\sum_{p=i}^jb_p) i=1∑k​j=i∑k​F(p=i∑j​bp​)

?(0) = 0; ?(1) = 1; ?(?) = ?(? − 1) + ?(? − 2), ? ≥ 2

答案对998244353取模。

?, ? ≤ 10^5, ??, ? ∈ [1,10^9]

题解：

如果没有操作四那都是SB东西。

考虑对于操作四怎么维护。

由斐波那契通项公式 F i = ( 1 + 5 2 ) i − ( 1 − 5 2 ) i 5 F_i=\dfrac{(\frac{1+\sqrt 5}{2})^i-(\frac{1-\sqrt 5}{2})^i}{\sqrt 5} Fi​=5 ​(21+5 ​​)i−(21−5 ​​)i​

考虑分别维护上面的两个次幂，很显然合并两条链只需要知道各自的答案，前缀积的和，后缀积的和，全部的积就行了。

然后考虑对于操作二，怎么计算操作四。

发现我们要求的是这个东西：

∑ i = 1 n ∑ j = i n q j − i + 1 \sum_{i=1}^n\sum_{j=i}^n q^{j-i+1} i=1∑n​j=i∑n​qj−i+1

其中 q q q是 ( 1 ± 5 2 ) x (\frac{1\pm \sqrt 5}{2})^x (21±5 ​​)x， x x x是操作的数。

发现是一个差比数列求和，直接算出来就行了。

设 x 1 = 1 + 5 2 x_1=\frac{1+\sqrt 5}{2} x1​=21+5 ​​，则长度为 k k k的链覆盖 i i i之后在 x 1 x_1 x1​上表现为 ( ( q − q k + 1 ) / ( 1 − q ) − k ) ∗ ( q / ( q − 1 ) ) ((q-q^{k+1})/(1-q)-k)*(q/(q-1)) ((q−qk+1)/(1−q)−k)∗(q/(q−1)) ，其中 q = x 1 i q=x_1^i q=x1i​

由于 5 5 5并不是模998244353意义下的二次剩余，所以需要利用复数来表示。

实际上我们只需要维护 1 + 5 2 \frac{1+\sqrt 5}{2} 21+5 ​​的幂次就行了。

因为 5 \sqrt 5 5 ​在模998244353意义下是虚数，并且平方是实数。

设 ( a + b 5 ) i = u + v 5 (a+b\sqrt 5)^i=u+v\sqrt 5 (a+b5 ​)i=u+v5 ​，则 ( a − b 5 ) i = u − v 5 (a-b\sqrt 5)^i=u-v\sqrt 5 (a−b5 ​)i=u−v5 ​

然后就没了，这个东西没有费马小定理，只能暴力快速幂，时间复杂度 O ( n log ⁡ 2 n ) O(n\log ^2n) O(nlog2n)

代码：

#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define ll long long
#define re register
#define gc get_char
#define cs constnamespace IO{inline char get_char(){static cs int Rlen=1<<22|1;static char buf[Rlen],*p,*p2;return (p==p2)&&(p2=(p=buf)+fread(buf,1,Rlen,stdin),p==p2)?EOF:*p++; }template<typename T>inline T get(){char c;while(!isdigit(c=gc()));T num=c^48;while(isdigit(c=gc()))num=(num+(num<<2)<<1)+(c^48);return num;}inline int gi(){return get<int>();}
}
using namespace IO;using std::cerr;
using std::cout;cs int mod=998244353;
inline int add(int a,int b){a+=b-mod;return a+(a>>31&mod);}
inline int dec(int a,int b){a-=b;return a+(a>>31&mod);}
inline int mul(int a,int b){ll r=(ll)a*b;return r>=mod?r%mod:r;}
inline int power(int a,int b,int res=1){for(;b;b>>=1,a=mul(a,a))(b&1)&&(res=mul(res,a));return res;
}
inline void Inc(int &a,int b){a+=b-mod;a+=a>>31&mod;}
inline void Dec(int &a,int b){a-=b;a+=a>>31&mod;}
inline void Mul(int &a,int b){a=mul(a,b);}
inline void ex_gcd(int a,int b,int &x,int &y){if(!b){x=1,y=0;return ;}ex_gcd(b,a%b,y,x);y-=a/b*x;
}
struct Map{static cs int magic=1898579;int key[magic],val[magic];Map(){memset(key,-1,sizeof key);}int locate(int k)cs{int h=k%magic;while(key[h]!=-1&&key[h]!=k)h=h+1==magic?0:h+1;return h;}int &operator[](int k){int h=locate(k);if(key[h]==-1){key[h]=k;val[h]=0;}return val[h];}bool count(int k)cs{return key[locate(k)]==k;}
}iv;
inline int inv(int a){if(!a)return 1;if(iv.count(a))return iv[a];int x,y;ex_gcd(a,mod,x,y);return iv[a]=(x%mod+mod)%mod;
}
cs int inv2=mod+1>>1,inv5=power(5,mod-2);// Fib_i= (((1+\sqrt 5)/2)^i-((1-\sqrt 5)/2)^i) / \sqrt 5
struct cp{int x,y;//x+ y * \sqrt 5cp(){}cp(int _x,int _y=0):x(_x),y(_y){}friend cp operator+(cs cp &a,cs cp &b){return cp(add(a.x,b.x),add(a.y,b.y));}friend cp operator-(cs cp &a,cs cp &b){return cp(dec(a.x,b.x),dec(a.y,b.y));}friend cp operator*(cs cp &a,cs cp &b){return cp(add(mul(a.x,b.x),mul(5,mul(a.y,b.y))),add(mul(a.x,b.y),mul(a.y,b.x)));}friend cp operator*(cs cp &a,int b){return cp(mul(a.x,b),mul(a.y,b));}void operator+=(cs cp &b){*this=*this+b;}void operator-=(cs cp &b){*this=*this+b;}void operator*=(cs cp &b){*this=*this*b;}void operator*=(int b){Mul(x,b),Mul(y,b);}
};
inline cp power(cp a,int b,cp res=cp(1)){for(;b;b>>=1,a=a*a)if(b&1)res=res*a;return res;
}
inline cp inv(cp a){return cp(a.x,dec(0,a.y))*inv(dec(mul(a.x,a.x),mul(5,mul(a.y,a.y))));
}
#define x1 x_1
cs cp sq5=cp(0,1),x1=cp(1,1)*inv2;cs int N=1e5+7;
int n,m;//长度为k的链覆盖i之后在x_1上表现为((q-q^{k+1})/(1-q)-k)*(q/(q-1)) ，其中q=x_1^i int fa[N],rev[N],son[N][2];
cp val[N],co[N];
int cd[N],siz[N];struct node{cp r,a;cp p,s;//sum of prefix and suffix on the chainnode(){}node(cs cp &val,int k=1){cp i1=inv(cp(1)-val);a=power(val,k);p=s=(val-a*val)*i1;r=(cp(k)-p)*val*i1;}void rev(){std::swap(p,s);}
};inline node operator*(cs node &l,cs node &r){node t;t.a=l.a*r.a;t.r=l.r+r.r+l.s*r.p;t.p=l.p+l.a*r.p;t.s=r.s+r.a*l.s;return t;
}node w[N];inline void pushup(int u){w[u]=node(val[u]);if(son[u][0])w[u]=w[son[u][0]]*w[u];if(son[u][1])w[u]=w[u]*w[son[u][1]];siz[u]=siz[son[u][0]]+siz[son[u][1]]+1;
}inline void pushrev(int u){rev[u]^=1;std::swap(son[u][0],son[u][1]);w[u].rev();
}inline void pushcover(int u,cs cp &t){cd[u]=1;co[u]=val[u]=t;w[u]=node(t,siz[u]);
}inline void pushdown(int u){if(rev[u]){if(son[u][0])pushrev(son[u][0]);if(son[u][1])pushrev(son[u][1]);rev[u]=0;}if(cd[u]){if(son[u][0])pushcover(son[u][0],co[u]);if(son[u][1])pushcover(son[u][1],co[u]);cd[u]=0;}
}inline bool isrt(int u){return son[fa[u]][0]!=u&&son[fa[u]][1]!=u;}
inline bool which(int u){return son[fa[u]][1]==u;}inline void Rotate(int u){int p=fa[u],pp=fa[p];bool d=which(u);if(!isrt(p))son[pp][which(p)]=u;son[p][d]=son[u][!d];if(son[u][!d])fa[son[p][d]]=p;son[u][!d]=p;fa[u]=pp,fa[p]=u;w[u]=w[p];pushup(p);
}inline void Splay(int u){static int q[N],qn;q[qn=1]=u;for(int re p=u;!isrt(p);p=fa[p])q[++qn]=fa[p];while(qn)pushdown(q[qn--]);for(int re p=fa[u];!isrt(u);Rotate(u),p=fa[u])if(!isrt(p))Rotate(which(u)==which(p)?p:u); 
}inline void access(int u){for(int re ch=0;u;ch=u,u=fa[u])Splay(u),son[u][1]=ch,pushup(u);
}inline void makert(int u){access(u);Splay(u);pushrev(u);
}inline void change(int u,int v){// set u->father to vmakert(1);access(u);Splay(u);fa[son[u][0]]=0;son[u][0]=0;pushup(u);fa[u]=v;
}inline void cover(int u,int v,int p){makert(u);access(v);Splay(v);pushcover(v,power(x1,p));
}inline int query1(int u){Splay(u);return add(val[u].y,val[u].y);
}inline int query2(int u,int v){makert(u);access(v);Splay(v);return add(w[v].r.y,w[v].r.y);
}signed main(){
#ifdef zxyoifreopen("st.in","r",stdin);
#else
#ifndef ONLINE_JUDGEfreopen("st.in","r",stdin);freopen("st.out","w",stdout);
#endif
#endifn=gi(),m=gi();for(int re i=1;i<=n;++i){int v=gi();val[i]=power(x1,v);w[i]=node(val[i]),siz[i]=1;}for(int re i=2;i<=n;++i)fa[i]=gi();while(m--){switch(gi()){case 1:{int u=gi(),v=gi();change(u,v);break;}case 2:{int u=gi(),v=gi(),x=gi();cover(u,v,x);break;}case 3:{int u=gi();printf("%d\n",query1(u));break;}case 4:{int u=gi(),v=gi();printf("%d\n",query2(u,v));break;}}}return 0;
}