正題
題目連結: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}^kFbi(\sum_{z=i}^jb_z)
\]
其中\(Fbi(i)\)表示第\(i\)個斐波那契數。輸出答案模\(998244353\)的值
\(1\leq n,m\leq 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}^jc_z-\sum_{i=1}^k\sum_{j=i}^k\prod_{z=i}^jd_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}^xu^i(x-i+1)=(x+1)\sum_{i=1}^xu^i-\sum_{i=1}^xu^ii
\[\Rightarrow (x+1)\frac{u^{x+1}-u}{u-1}-\frac{xu^{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;
}