正題

題目鏈接:http://www.ybtoj.com.cn/contest/125/problem/2

---

題目大意

給出$n$個點的一棵樹，以$1$為根，每個點有點權$a_i$。要求支持$m$次操作

修改一個修改一個節點的父節點

修改一條路徑的權值為$w$

給出$u$詢問$Fbi(a_u)$

給出$u,v$，將路徑$u?>v$的點權排列好后設為$b$求
$$\sum _{i=1}^k\sum _{j=i}^{k}Fbi(\sum _{z=i}^j{b}_z)$$

其中$Fbi(i)$表示第$i$個斐波那契數。輸出答案模$998244353$的值

$1\le n,m\le 10^5,a_i,w\in [1,10^9]$

---

解題思路

嗯這個斐波那契很麻煩，可以考慮一些用特征方程$1?x?x^2=0$，可以得到斐波那契的通項公式
$$Fbi(n)=\frac{(\frac{\sqrt{5}+1}{2}{)}^n?(\frac{\sqrt{5}?1}{2}{)}^n}{\sqrt{5}}$$
為了方便上面$\frac{\sqrt{5}\pm 1}{2}$分別記為$X_0,X_1$。
那么如果設$c_i=X_0^{a_i},d_i=X_1^{a_i}$的話我們要求的就是
$$\frac{{\sum }_{i=1}^k{\sum }_{j=i}^k{\prod }_{z=i}^j{c}_z?{\sum }_{i=1}^k{\sum }_{j=i}^k{\prod }_{z=i}^j{d}_z}{\sqrt{5}}$$
這個好像看起來好維護一點，不過首先我們要解決這個$\sqrt{5}$的問題，因為其實$\sqrt{5}$在模$998244353$意義下是沒有值的，我們不能直接用二次剩余帶入數字。

考慮維護一個類似于多項式的東西，每個數字記為二元組$(a,b)=a\sqrt{5}+b$。加減乘都很好搞，除法的話需要推導一下，
$$\frac{1}{a\sqrt{5}+b}=c\sqrt{5}+d$$
$$5ac+\sqrt{5}(ad+cb)+bd=1$$
$$5ac+bd=1,ad+cb=0$$
解出來$$c=?\frac{a}{b^2?5a^2},d=\frac{b}{b^2?5a^2}$$
這樣四則運算都搞定了，可以開始考慮如何在$LCT$上面維護了。

類似線段樹的，設$pro$表示所有數乘積，$pre/suf$表示所有前/后綴乘積和，$ans$表示我們維護的答案，那么就可以合并兩個東西了。$LCT$維護的時候順便把單個的節點也合并進去就好了。

然后還剩下一個最麻煩的東西就是樹鏈修改的時候我們需要快速算出連續$x$個$u$的信息。
$pro$很好搞就是$u^x$，$suf$和$pre$就是一個簡單的等比數列求和，上通項公式就好了。
$ans$比較麻煩，考慮每個$u^i$的個數答案就是
$$\sum _{i=1}^x{u}^i(x?i+1)=(x+1)\sum _{i=1}^x{u}^i?\sum _{i=1}^x{u}^{i}i$$
$$?(x+1)\frac{u^{x+1}?u}{u?1}?\frac{x{u}^{x+1}?\frac{u^x?u}{u?1}}{u?1}$$
這樣就可以在$log$時間復雜度以內合并了。

然后答案$0$次項一定是$0$的，所以輸出$\sqrt{5}$的項就好了。
時間復雜度$O(n{\log }^{2}n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<stack> #define ll long long using namespace std; const ll P=998244353,N=1e5+10; struct node{ll a,b;//a帶√5 node(ll aa=0,ll bb=0){a=aa;b=bb;return;} }; ll power(ll x,ll b=P-2){ll ans=1;x%=P;while(b){if(b&1)ans=ans*x%P;x=x*x%P;b>>=1;}return ans; } const node X((P+1)/2,(P+1)/2); node operator+(node x,node y) {return node((x.a+y.a)%P,(x.b+y.b)%P);} node operator-(node x,node y) {return node((x.a-y.a)%P,(x.b-y.b)%P);} node operator*(node x,node y) {return node((x.a*y.b+x.b*y.a)%P,(x.b*y.b+5*x.a*y.a)%P);} node inv(node x){ll tmp=power(x.b*x.b-5*x.a*x.a);return node(-x.a,x.b)*node(0,tmp); } node power(node x,ll b){node ans(0,1);while(b){if(b&1)ans=ans*x;x=x*x;b>>=1;}return ans; } struct Tnode{node ans,pre,suf,pro; }; Tnode operator+(Tnode x,Tnode y){Tnode w;w.ans=x.ans+y.ans+x.suf*y.pre;w.pre=x.pre+y.pre*x.pro;w.suf=y.suf+x.suf*y.pro;w.pro=x.pro*y.pro;return w; } struct SegTree{ll fa[N],t[N][2],siz[N];Tnode w[N];node v[N],lazy[N];bool r[N],hlz[N];stack<ll> s;bool Nroot(ll x){return fa[x]&&(t[fa[x]][0]==x||t[fa[x]][1]==x);}bool Direct(ll x){return t[fa[x]][1]==x;}void Rev(ll x){swap(t[x][0],t[x][1]);swap(w[x].pre,w[x].suf);r[x]^=1;return;}void PushUp(ll x){siz[x]=siz[t[x][0]]+siz[t[x][1]]+1;w[x]=(Tnode){v[x],v[x],v[x],v[x]};if(t[x][0])w[x]=w[t[x][0]]+w[x];if(t[x][1])w[x]=w[x]+w[t[x][1]];return;}void Updata(ll x,node u){ll s=siz[x];lazy[x]=v[x]=u;node tmp=inv(node(0,1)-u);hlz[x]=1; w[x].pro=power(u,s);w[x].pre=w[x].suf=(u-w[x].pro*u)*tmp;w[x].ans=(node(0,s)-w[x].pre)*u*tmp;return;}void PushDown(ll x){if(hlz[x]){if(t[x][0])Updata(t[x][0],lazy[x]);if(t[x][1])Updata(t[x][1],lazy[x]);hlz[x]=0;}if(!r[x])return;Rev(t[x][0]);Rev(t[x][1]);r[x]=0;return;}void Rotate(ll x){ll y=fa[x],z=fa[y];ll xs=Direct(x),ys=Direct(y);ll w=t[x][xs^1];if(Nroot(y))t[z][ys]=x;t[x][xs^1]=y;t[y][xs]=w;if(w)fa[w]=y;fa[y]=x;fa[x]=z;PushUp(y);PushUp(x);return;}void Splay(ll x){ll y=x;s.push(x);while(Nroot(y))y=fa[y],s.push(y);while(!s.empty())PushDown(s.top()),s.pop();while(Nroot(x)){ll y=fa[x];if(!Nroot(y))Rotate(x);else if(Direct(x)==Direct(y))Rotate(y),Rotate(x);else Rotate(x),Rotate(x);}return;}void Access(ll x){for(ll y=0;x;y=x,x=fa[x])Splay(x),t[x][1]=y,PushUp(x);return;}void MakeRoot(ll x){Access(x);Splay(x);Rev(x);return;}void Link(ll x,ll y){MakeRoot(1);Access(x);Splay(x);fa[t[x][0]]=0;t[x][0]=0;PushUp(x);fa[x]=y;return;}ll Split(ll x,ll y){MakeRoot(x);Access(y);Splay(y);return (w[y].ans.a+P)%P*2%P;}void Change(ll x,ll y,node val){MakeRoot(x);Access(y);Splay(y);Updata(y,val);return;} }T; ll n,m; signed main() { // freopen("fibonacci.in","r",stdin); // freopen("fibonacci.out","w",stdout);scanf("%lld%lld",&n,&m);for(ll i=1;i<=n;i++){ll x;scanf("%lld",&x);T.v[i]=power(X,x);T.PushUp(i);}for(ll i=2;i<=n;i++)scanf("%lld",&T.fa[i]);while(m--){ll op,u,v,w;scanf("%lld",&op);if(op==1){scanf("%lld%lld",&u,&v);T.Link(u,v);}else if(op==2){scanf("%lld%lld%lld",&u,&v,&w);T.Change(u,v,power(X,w));}else if(op==3){scanf("%lld",&u);printf("%lld\n",T.Split(u,u));}else if(op==4){scanf("%lld%lld",&u,&v);printf("%lld\n",T.Split(u,v));}}return 0; }

總結

以上是生活随笔為你收集整理的YbtOJ#732-斐波那契【特征方程,LCT】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。